4

私は問題を抱えていますが、同様のタスクを実行しようとした他の人を見つけることができないようです。int配列grid[][]に数値のグリッドがあります

2 5 1 0 8 0 8
2 1 0 9 7 2 4
3 6 2 3 4 9 7
3 3 3 4 7 8 9
3 3 1 2 3 1 4
9 7 4 1 2 3 4

上、下、左、右に行くだけで接続されている数字が最も多い場所を見つけるための簡単なアルゴリズムが必要です。したがって、上記の例では、インデックス[2][0]に3が見つかります。

ifステートメントとループをループごとに実行するだけで問題を解決できることはわかっていますが、それは非常に反復的ですが、これを実行するより簡単な方法があるかどうか疑問に思っていましたか？

どんな助けでもありがたいです、これは私が作成しているゲームのためのものです。ありがとうございました ：）

編集：この問題を解決するのに役立ちます。

2 5 1 0 8 0 8
2 1 0 9 7 2 4
3 6 2 3 4 9 7
3 3 3 4 7 8 9
3 3 1 2 3 1 4
9 7 4 1 2 3 4

このメソッドは、答えとして0,2を返します。

3
3 3 3
3 3

最も隣接する番号があります

もう一つの例、

2 5 1 0 8 0 8
2 1 0 9 7 2 4
3 3 3 3 4 6 7
1 0 3 4 7 4 9
3 3 3 2 3 1 6
9 7 4 1 8 4 6

完全な検索は

3 3 3 3
    3
3 3 3

これまでのすべての回答に感謝します。深さ優先探索は面白そうに見えますが、これまでのところ、ツリースタイルの検索に関する情報しか見つけることができません。

4

6 に答える 6

1

フラッド フィル可能な最大の領域だけが必要な場合は、標準のフラッド フィル アルゴリズムを使用して、フィルしたノードの数を数えながら、再びアクセスしてはならないことを示す値でそれらを埋めることができます。これは配列用であり、最適である必要があります。O(n2)n x n

最大の領域ではなく、最長のシーケンスが必要な場合は、各フラッド フィル領域内で最長のハミルトニアン パスを検索する必要があります。Alon Itai、Christos H. Papadimitriou、および Jayme Luiz Szwarcfiter による「Hamilton Paths in Grid Graphs (1982)」によると、残念ながら運が悪いとのことです。非ペイウォール バージョンは見つかりませんでしたが、アブストラクトは十分に明確に見えます。(もちろん、問題が NP 完全であるという事実は、その問題が解決できないという意味ではありません。おそらく、N は十分に小さいため、実用的です。)

于 2013-03-13T19:49:32.817 に答える
1

たぶん、このようなものは小さな調整でうまくいくでしょう。自分で実行したことはありませんが、コンセプトは明確なはずです。同じスペースが複数回評価される可能性があるため、最適化することもできます。

public class FindConsecutiveNumbersInGrid {

public static int[][] grid = new int[][]{
    {2, 5, 1, 0, 8, 0, 8},
    {2, 1, 0, 9, 7, 2, 4},
    {3, 3, 3, 3, 4, 6, 7},
    {1, 0, 3, 4, 7, 4, 9},
    {3, 3, 3, 2, 3, 1, 6},
    {9, 7, 4, 1, 8, 4, 6}
};

public static void main(String[] args) {
    int maxFound = 0;
    int[] maxFoundPos = new int[2];
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            boolean[][] foundGrid = new boolean[grid.length][grid[0].length];
            findConsecutive(i, j, foundGrid);
            int found = getFound(foundGrid);
            if (found > maxFound) {
                maxFound = found;
                maxFoundPos[0] = i;
                maxFoundPos[1] = j;
            }
        }
    }
    System.out.println(maxFoundPos[0] + " " + maxFoundPos[1]);
}

public static void findConsecutive(int i, int j, boolean[][] foundGrid) {
    foundGrid[i][j] = true;
    if (i < grid.length - 1 && grid[i][j] == grid[i+1][j] && !foundGrid[i+1][j]) {
        findConsecutive(i+1, j, foundGrid);
    }
    if (i > 0 && grid[i][j] == grid[i-1][j] && !foundGrid[i-1][j]) {
        findConsecutive(i-1, j, foundGrid);
    }
    if (j < grid[i].length - 1 && grid[i][j] == grid[i][j+1] && !foundGrid[i][j+1]) {
        findConsecutive(i, j+1, foundGrid);
    }
    if (j > 0 && grid[i][j] == grid[i][j-1] && !foundGrid[i][j-1]) {
        findConsecutive(i, j-1, foundGrid);
    }
}

public static int getFound(boolean[][] foundGrid) {
    int found = 0;
    for (boolean[] foundRow : foundGrid) {
        for (boolean foundSpace : foundRow) {
            if (foundSpace) found++;
        }
    }
    return found;
}

}

これにより、正しく「2 0」が出力されます。

于 2013-03-13T20:01:43.093 に答える
0

これを動的計画問題として定式化できます

すべてのi、jについて、昇順path [i] [j]=1である隣接パスの数を計算します 

for i=0;i<n 
  for j=0;j<n
     for dirx, diry in [(1,0),(0,1) ... etc ... ]
        if arr[i+dirx][j+diry] = arr[i][j] + 1
           path[i+dirx][j+diry] += path[i][j]

答えはmax(path[i][j])すべてのi、jになります。

または再帰的に、必要に応じて

   for i,j<n
       go(i,j)

   def go(i,j)
        if path[i][j]>0 return path[i][j]
        ret = 1;
        for dirx, diry in [(1,0),(0,1) ... etc ... ]

            if arr[i+dirx][j+diry] = arr[i][j] + 1
               ret = max(ret, go(i+dirx,j+diry))

        return ret
于 2013-03-13T19:43:56.687 に答える
0

最初に未訪問のセルを見つけ、再帰を開始します。免責事項: これは Java ではなく、ほとんどの宣言とヘッダーがない疑似 C です。とにかくCはJavaに変換する方がずっと簡単です...必要に応じて、カウントにグローバルまたはクラスメンバーを使用してください。

簡単にするために、N*N 配列をガードで囲みます。

    // with -1 -1 -1 -1 
    //      -1  x  x -1
    //      -1 -1 -1 -1

for (i=N+2;i<(N+2)*(N+1);i++) { // exact starting and ending locations are disclosed
  if (k=array[i]!=-1) {
      j=1;
      flood_fill(array,i,k,&j);
      if (j>max) { max=j; max_number=k; }
  }
}

#define UP -(N+2)
#define DOWN (N+2)
#define LEFT -1
#define RIGHT 1

int flood_fill(int *array, int position, int value_to_compare, int *count)
{
    // for each direction UP,DOWN,RIGHT,LEFT 
    static const int directions[4]={UP,DOWN,RIGHT,LEFT];
    int t;
    for (t=0;t<4;t++)
    if (array[position + directions[t]]==value_to_compare) {
        array[position + directions[t]] = -1;
        *count+=1;
        flood_fill(array, position+directions[t], value_to_compare, count);
    }
}
于 2013-03-13T19:53:21.623 に答える
0

右に下に移動して接続された最も連続した数字がある場所を見つけるための単純なアルゴリズムが必要です。

単純なアルゴリズムは、行と列をループして、最も長いシーケンスを下と右に探すことです。

最初のオカレンスのみが必要なので、左または上を見る必要はありません。

見つかった最長の文字列よりも小さいインデックスに到達すると、ループを中断できます。つまり、3 文字の文字列が見つかったら、最後の 2 列と最後の 2 行をループする必要はありません。

ただし、マトリックス全体をループする方が、ほぼ同じくらい速く、はるかに簡単です。

この例では、(2,0) に 1 つ、(3,0) に 1 つ、3 つの 3 つの文字列が 2 つ見つかります。最初の答えを最終的な答えとして受け入れるだけです。

于 2013-03-13T19:41:45.040 に答える