java - 根据 char[][] 数组提供的规则创建邻接矩阵

Question

我想将一个char[][] 数组(我们称它为cA)变成一个邻接矩阵。邻接矩阵的列和行等于数组中元素的数量，邻接矩阵中的每个顶点要么是 true 要么是 false，具体取决于初始元素中的元素数组是相邻的。我想稍微改变一下规则，并将邻接矩阵顶点限制为真，前提是元素相邻并且其中一个元素不是特定值。

cA 数组如下所示:

z y z
z z z
z y y

cA 数组的邻接矩阵(我们称之为 aM)将是一个 int 数组，大小为 [3* 3][3*3]。 aM(i,j) 为 true 的条件是 中的元素 i 和 j >cA 数组必须相邻，但i 或j 都不能为"y"。

让 cA 数组元素从 1 到 9 编号。

1 2 3
4 5 6
7 8 9

aM 可以通过以下操作来描述:

aM(1,1) //false, no self-adjacency
aM(1,2) //false, 2 is a "y"
aM(1,3) //false, 1 is not adjacent to 3
aM(1,4) //true, 1 is adjacent to 4, neither are "y"
aM(1,5) //false, 1 is not adjacent to 5
aM(1,6) //false, 1 is not adjacent to 6
aM(1,7) through aM(1,9) //false, there is no adjacency between 1 and 7, 8, or 9
aM(2,1) through aM(2,9) //false, 2 is a "y"
...

希望你明白了。综上所述，cA 的邻接矩阵如下:

   1 2 3 4 5 6 7 8 9 (i)
 1 0 0 0 1 0 0 0 0 0
 2 0 0 0 0 0 0 0 0 0
 3 0 0 0 0 0 1 0 0 0
 4 1 0 0 0 1 0 1 0 0
 5 0 0 0 1 0 1 0 0 0
 6 0 0 1 0 1 0 0 0 0
 7 0 0 0 1 0 0 0 0 0
 8 0 0 0 0 0 0 0 0 0
 9 0 0 0 0 0 0 0 0 0
(j)

规则是 aM(i,j) == 1 当且仅当 i != j, i != "y"&& j != "y "，并且 i 和 j 彼此相邻。

我在编造一个算法来创建一个提供 char[][] 数组的邻接矩阵时遇到了困难。我已经定义了规则，但是找到迭代的约束是有问题的。

Answer 1

试试这个:

static void set(boolean[][] aM, int cols, int row0, int col0, int row1, int col1) {
    int index0 = row0 * cols + col0;
    int index1 = row1 * cols + col1;
    aM[index0][index1] = aM[index1][index0] = true;
}

static boolean[][] adjacencyMatrix(char[][] cA) {
    int rows = cA.length;
    int cols = cA[0].length;
    boolean[][] aM = new boolean[rows * cols][rows * cols];
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (cA[i][j] == 'y')
                continue;
            if (i + 1 < rows && cA[i + 1][j] != 'y')
                set(aM, cols, i, j, i + 1, j);
            if (j + 1 < cols && cA[i][j + 1] != 'y')
                set(aM, cols, i, j, i, j + 1);
        }
    }
    return aM;
}

public static void main(String[] args) {
    char[][] cA = {
        {'z', 'y', 'z'},
        {'z', 'z', 'z'},
        {'z', 'y', 'y'},
    };
    boolean[][] aM = adjacencyMatrix(cA);
    for (boolean[] row : aM) {
        for (boolean cell : row)
            System.out.print(cell ? "1" : "0");
        System.out.println();
    }
}

结果是:

000100000
000000000
000001000
100010100
000101000
001010000
000100000
000000000
000000000