0

次のような 2 次元配列があります。

1 1 0 0 1
1 0 1 1 0
0 0 1 1 0
1 1 0 1 1
0 0 1 1 1

横方向または下方向に連続する 1 の最長のチェーンを特定する方法を見つけようとしています。この場合、列 4、行 2 から始まり、その長さは 4 で下に向かっています。

再帰を使用することを考えていましたが、特に 0 に遭遇したときに、位置を追跡する際に問題が発生しています。

これまでのところ、私はこれに沿ったものを持っています（全体をチェックするためだけに）：

main() {
    ...
    for(i = 0; i < n; i++)
      for(j = 0; j < n; j++)
        if (G[i][j] == 1) {
          CheckAcross(i, j, n);
        }
    ...
}

void CheckAcross (int i, int j, int n) {
     if (i < 0 || i >= n || j < 0 || j >= n) return; // outside of grid
     if (G[i][j] == 0 ) return; //0 encountered
     G[i][j] = WordCount + 1;
     CheckAcross(i, j + 1, n);

}

ここG[][]で、 は 1 と 0 を含む 2 次元配列n、 は行/列のi数、 は行番号、jは列番号です。

事前にご協力いただきありがとうございます。

4

2 に答える 2

0

V という新しい n 行 n 列の行列を作成します。これにより、セルごとに、そのセルとそのすぐ上の 1 の数が格納されます。これは O(n^2) になります。

checkAllVertical(int n) {
    V = malloc(....) // create V, an n-by-n matrix initialized to zero
    for(int r=0; r<n; r++) {
      for(int c=0; c<n; c++) {
        if(G[r][c]=1) {
          if(r==0)
            V[r][c] = 1;
          else
            V[r][c] = 1 + V[r][c];
        }
      }
    }
}

V のすべてを実際に割り当てる必要はありません。一度に 1 行で十分です。

于 2011-05-14T18:59:57.273 に答える
0

現在の回答には O(n 3 ) 時間がかかります。単一の行を評価するには、可能なすべての開始位置と終了位置 (それぞれに O(n) の可能性) をチェックし、n 行あります。

あなたのアルゴリズムは正しいですが、実行時間を改善できるかどうか見てみましょう。

この問題をより単純な問題に分割すると、問題がより単純になる可能性があります。つまり、「この 1 次元配列で最も長く連続する 1 の連鎖は?」です。何回も解けば答えが得られるので、改善のためにはこれを O(n 22n )よりも小さくする必要があります。

さて、最も長い 1 のシーケンスの位置 (開始と終了) と長さを覚えて、単純に行をたどることができます。これには O(n) 時間がかかり、最適です (シーケンスがすべて 1 または 0 の場合、最長シーケンスの開始/終了がどこにあるかを知るためにすべての要素を読み取る必要があります)。

次に、すべての行とすべての列について、O(n 2 ) 時間で簡単に解くことができます。

于 2011-05-12T04:27:56.153 に答える