2

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

        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;
                        }
                    }
                }
        }

输出点为 start(5,5) end(8,8) 的 10x10 网格：

00007670000
00076567000
00765456700
07654345600
76543234560
65432123456
76543234560
07654345600
00765456700
00076567000
00007670000

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

4

2 回答 2

1

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

我运行了您的示例，并将代码附加到开头：

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

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

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

我计时了超过一百万次运行，并获得了约 20% 的加速。

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

于 2013-11-13T20:20:18.960 回答
1

例如，每当您访问您的g数组时，都会在后台进行两次边界检查。如果边界检查失败，则抛出。g[i][j]java.lang.IndexOutOfBoundsException

您可以将边界检查的数量减少一半。

g[W][H]您可以使用简单的一维数组，而不是使用二维数组g[W*H]。然后，g[i][j]你可以写而不是写g[i*W + j]。

于 2013-11-14T18:44:44.390 回答