// 第 3 周 – 二维数组（矩阵）
// 运行：java Matrix.java
public class Matrix {

    static void print(int[][] m) {
        for (int[] row : m) {
            for (int v : row) System.out.printf("%4d", v);
            System.out.println();
        }
    }

    // 主对角线（i == j）和副对角线（i + j == n - 1）元素之和 – O(n)
    static int[] diagonalSums(int[][] m) {
        int n = m.length, main = 0, anti = 0;
        for (int i = 0; i < n; i++) {
            main += m[i][i];
            anti += m[i][n - 1 - i];
        }
        return new int[] { main, anti };
    }

    // 转置：行变成列 – O(n·m)
    static int[][] transpose(int[][] m) {
        int rows = m.length, cols = m[0].length;
        int[][] t = new int[cols][rows];
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                t[j][i] = m[i][j];
        return t;
    }

    // 矩阵乘法：（n×k） · (k×m) = (n×m) – O(n·k·m)，方阵为 O(n³)
    static int[][] multiply(int[][] a, int[][] b) {
        int n = a.length, k = b.length, m = b[0].length;
        int[][] c = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int x = 0; x < k; x++)
                    c[i][j] += a[i][x] * b[x][j];
        return c;
    }

    // 用一维数组模拟行优先存储：
    // A[i][j] 的位置是 i * cols + j
    static int get(int[] flat, int cols, int i, int j) {
        return flat[i * cols + j];
    }

    public static void main(String[] args) {
        int[][] m = {
                { 1, 2, 3 },
                { 4, 5, 6 },
                { 7, 8, 9 } };
        System.out.println("m:");
        print(m);
        int[] ds = diagonalSums(m);
        System.out.println("main diagonal sum = " + ds[0] + ", anti-diagonal sum = " + ds[1]);

        int[][] r = { { 1, 2, 3 }, { 4, 5, 6 } };
        System.out.println("transpose of r (2x3) (3x2):");
        print(transpose(r));

        int[][] id = { { 1, 0, 0 }, { 0, 1, 0 }, { 0, 0, 1 } };
        System.out.println("r · I:");
        print(multiply(r, id));

        // 在 Java 中二维数组实际上是“数组的数组” – 各行的长度可以不同
        int[][] jagged = new int[3][];
        jagged[0] = new int[] { 1, 2, 3 };
        jagged[1] = new int[] { 4, 5 };
        jagged[2] = new int[] { 6, 7, 8, 9 };
        System.out.println("jagged array:");
        print(jagged);

        // 行优先表示
        int[] flat = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        System.out.println("flat[1*3 + 2] = A[1][2] = " + get(flat, 3, 1, 2));
    }
}