java - 如何从二维数组中的一个点增加相邻单元格

Question

我正在努力使李氏算法的实现更加高效，到目前为止，我正在使用立方循环来递增我的二维整数数组中的相邻单元格:

        for(int k = 1; k < g.length*2; ++k){
            for(int i = x0-k; i < x1+k; ++i)
                for(int j = y0-k; j < x1+k; ++j)
                {
                    if(i > 0 && j > 0 && i < g.length-1 && j < g.length-1)
                    {
                        if(g[x1][y1] != 0)
                            return true;    
                        if(g[i][j] == k && g[i+1][j] == 0){
                            g[i+1][j] = k + 1;
                        }
                        if(g[i][j] == k && g[i][j+1] == 0){
                            g[i][j+1] = k + 1;
                        }
                        if(g[i][j] == k && g[i-1][j] == 0){
                            g[i-1][j] = k + 1;
                        }
                        if(g[i][j] == k && g[i][j-1] == 0){
                            g[i][j-1] = k + 1;
                        }
                    }
                }
        }

带有点开始(5,5)结束(8,8)的 10x10 网格的输出:

00007670000
00076567000
00765456700
07654345600
76543234560
65432123456
76543234560
07654345600
00765456700
00076567000
00007670000

有没有更快的方法来填充网格并同时检查值？

Answer 1

我对这个算法知之甚少，但一些 Material 建议你选择你的起点作为离图形中心最远的点。

我运行了您的示例，并在开头附加了以下代码:

if (d2 > d1) {
    startRow = startRow ^ endRow;
    endRow = startRow ^ endRow;
    startRow = startRow ^ endRow;

    startCol = startCol ^ endCol;
    endCol = startCol ^ endCol;
    startCol = startCol ^ endCol;
}

d2 和 d1 分别是终点和起点到中心的距离。

我将其计时超过 100 万次，并获得了约 20% 的加速。

他们建议的另一个选择是同时从起点和终点散开 - 但我不确定它的停止条件是什么(因为目标将从代码中的 1 开始).