2

私がやりたいのは、次のような閉じたスパイラル パターンで行列を通過するアルゴリズムです。

1 | 2 | 3
---------
8 | 9 | 4
---------
7 | 6 | 5

この問題に取り組む最も簡単な方法は何ですか?

私の考え：

  • コーナーまたは障害物の検出。
  • 垂直方向と逆方向に下降するプログラム的な方法があります。
  • 要素が既に訪問されたことを検出する方法を用意してください。

PS: サイズが正方形でない場合や幅が偶数の場合の処理​​方法がわかりません。

4

3 に答える 3

5

各セルに訪問済みの概念は必要ありません。現在の距離を示す変数が 1 つあれば十分です。

以下は、これを行うための (十分にテストされていない) Java コードです。

それはかなり読みやすいはずです。

  // initialize
  int w = 5, h = 7;
  int[][] arr = new int[w][h];

  // do the work
  int count = 1;
  for (int i = 0; count <= w*h; i++)
  {
     // go right
     for (int x = i; x < w-i && count <= w*h; x++)
        arr[x][i] = count++;

     // go down
     for (int y = i+1; y < h-i && count <= w*h; y++)
        arr[w-i-1][y] = count++;

     // go left
     for (int x = w-2-i; x >= i && count <= w*h; x--)
        arr[x][h-i-1] = count++;

     // go up
     for (int y = h-2-i; y > i && count <= w*h; y--)
        arr[i][y] = count++;
  }

ジャバ。

出力：

  1  2  3  4  5
 20 21 22 23  6
 19 32 33 24  7
 18 31 34 25  8
 17 30 35 26  9
 16 29 28 27 10
 15 14 13 12 11
于 2013-08-13T17:30:03.710 に答える
1

再帰的に、正当な理由もなく:

right()、down()、left()、という名前の 4 つの関数を使用しup()ます。

このright()関数は、行列の一番上の行に沿ってカウントし、残りの行 (ちょうど入力した行を除くすべて) を に渡し down()ます。

このdown()関数は、行列の右端をカウント ダウンし、残りの列を に渡しますleft()。

等

幅または高さがゼロになると、再帰は停止します。

于 2013-08-13T18:33:41.017 に答える
1

セルごとに、すぐに垂直および水平位置にある空/訪問済みセルの数を示す数値を持ちます (それを と呼びましょうnumVisitedAroundCell)。また、ブール値フラグ を持ちisVisitedます。セルを調べて更新しますnumVisitedAroundCell（したがって、コーナーセルには がnumVisitedAroundCell == 2あり、コーナーではないセルの外側のレイヤーには がありますnumVisitedAroundCell == 1）

セルを調べて、 のセルになるコーナー セルを見つけますnumVisitedAroundCell == 2。

isVisitedそこから、渡す各セルを としてマークし、 の数を増やしながら、垂直または水平に移動しますnumVisitedAroundCell。選択したパスをコーナー セルに到達するまで進み (このコーナー セルにnumVisitedAroundCell到達すると、3 になるはずです)、次の未訪問のセルを見つけて、そのルートを進みます。これを続けていれば、あなたが望んでいたスパイラルが得られると思います。また、これは、幅が均一で、サイズが正方形でない場合に対処する必要があります。

于 2013-08-13T17:31:21.257 に答える