2

Lee のアルゴリズムの実装をより効率的にしようとしていますが、これまでのところ、3 乗ループを使用して 2D 整数配列内の隣接するセルをインクリメントしています。

        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

たとえば、g配列にアクセスしているときはいつでも、boundaryの内部チェックが2 つあります。境界チェックに失敗した場合はスローされます。g[i][j]java.lang.IndexOutOfBoundsException

境界チェックの数を半分に減らすことができます。

2D 配列を使用する代わりに、g[W][H]単純な 1D 配列を使用できますg[W*H]。次に、 と書く代わりに、 と書くg[i][j]ことができますg[i*W + j]。

于 2013-11-14T18:44:44.390 に答える