DFSアルゴリズムを使用して行列内の隣接する数値の最大面積を見つける

Question

私は初心者のための本を使ってプログラミングを学習しています。配列の後の私の最後の仕事は：

// Find the biggest area of adjacent numbers in this matrix: 
int[][] matrix = { 
     {1,3,2,2,2,4}, 
     {3,3,3,2,4,4}, 
     {4,3,1,2,3,3}, // --->13 times '3'; 
     {4,3,1,3,3,1}, 
     {4,3,3,3,1,1} 

私は持っているヒント--DFSまたはBFSアルゴリズムを使用します。私がそれらについて読んだあと、多くの実装を見た後、私はそのアイデアを得ましたが、初心者にとっては圧倒されました。私は自分の仕事のための解決策を見つけました。何度もプログラムを実行した後、私はそれがどのように機能しているのか理解しました。今は自分で問題を解決することができます。このソリューションが再帰について学ぶのを助けてくれたことは嬉しいですが、次のコードを反復的に変更することができますか？前もって感謝します。

public class Practice { 

private static boolean[][] visited = new boolean[6][6]; 
private static int[] dx = {-1,1,0,0}; 
private static int[] dy = {0,0,-1,1}; 
private static int newX; 
private static int newY; 

public static void main(String[] args){ 
// Find the biggest area of adjacent numbers in this matrix: 
int[][] matrix = { 
     {1,3,2,2,2,4}, 
     {3,3,3,2,4,4}, 
     {4,3,1,2,3,3}, // --->13 times '3'; 
     {4,3,1,3,3,1}, 
     {4,3,3,3,1,1} 

}; 

int current = 0; 
int max = 0; 

for (int rows = 0; rows < matrix.length;rows++){ 
    for(int cols = 0; cols < matrix[rows].length;cols++){ 

     if (visited[rows][cols] == false){ 
      System.out.printf("Visited[%b] [%d] [%d] %n", visited[rows] 
     [cols],rows,cols); 
      current = dfs(matrix,rows,cols,matrix[rows][cols]); 
      System.out.printf("Current is [%d] %n", current); 
      if(current > max){ 
       System.out.printf("Max is : %d %n ", current); 
       max = current; 
      } 

     } 
    } 
}  
     System.out.println(max); 
} 
static int dfs(int[][] matrix,int x, int y, int value){   

    if(visited[x][y]){ 
     System.out.printf("Visited[%d][%d] [%b] %n",x,y,visited[x][y]); 
     return 0; 
    } else { 
     visited[x][y] = true; 
     int best = 0; 
     int bestX = x; 
     int bestY = y; 

     for(int i = 0; i < 4;i++){ 
      //dx = {-1,1,0,0}; 
      //dy = {0,0,-1,1}; 
      int modx = dx[i] + x; 
      System.out.printf(" modx is : %d %n", modx); 
      int mody = dy[i] + y; 
      System.out.printf(" mody is : %d %n", mody); 
      if(modx == -1 || modx >= matrix.length || mody == -1 || mody >= 
      matrix[0].length){ 
       continue; 
      } 
      if(matrix[modx][mody] == value){ 
       System.out.printf("Value is : %d %n",value); 
       int v = dfs(matrix,modx,mody,value); 
       System.out.printf(" v is : %d %n",v); 
       best += v; 
       System.out.printf("best is %d %n",best); 
      } 

      newX = bestX; 
      System.out.printf("newX is : %d %n",newX); 
      newY = bestY; 
      System.out.printf("newY is : %d %n",newY); 
     } 
     System.out.printf("Best + 1 is : %d %n ",best + 1); 
      return best + 1; 
    } 


} 
} 

Answer 1

あなたは擬似コードセクションの下Depth-first searchのためのWikipediaのページに見れば、彼らはDFSアルゴリズムの反復verisionの例を持っています。そこから解決策を見つけ出すことができるはずです。

*編集

では、次の操作を行うことができ、それが反復的にするには：

procedure DFS-iterative(matrix, x, y): 
    let S be a stack 
    let value = 0 
    if !visited[v.x, v.y] 
    S.push(position(x,y)) 
    while S is not empty 
    Position v = S.pop() 
    value += 1 
    for all valid positions newPosition around v 
     S.push(newPosition) 
    return value 

毎回あなたが再帰的な方法でdfs()メソッドを呼び出すと、あなたはS.push()を呼び出す必要があります。あなたは

class Position{ 
    int x; 
    int y; 
    public Position(int x, int y){ 
    this.x = x; 
    this.y = y; 
    } 
    //getters and setters omitted for brevity 
} 

を次のようにクラスのポジションを作成し、それを簡単にするために、Javaクラスjava.util.Stackで構築を使用することができます。

Stack<Position> s = new Stack<Position>();

あなたの代わりにDFSのBFSを使用したい場合は、キューへの簡単な変更スタックすることができますし、望ましい結果を得るでしょう。 This linkには、スタックとキューの説明があり、トピックについて学ぶときに役立ちます。

Answer 2

DFSがすでに動作していて、BFSが反復的である（または少なくとも再帰的に実装するのが簡単な）反復的なので、あなたはBFSソリューションを探していると仮定します。

地域の大きさを測定する（未テスト）BFSコードは次のようになります。あなたは、単一の行を変更することで、反復DFSへ（キューベース）BFSを変更することができます

public static int regionSize(int[][] matrix, 
     int row, int col, HashSet<Point> visited) { 

    ArrayDeque<Point> toVisit = new ArrayDeque<>(); 
    toVisit.add(new Point(col, row)); 
    int regionColor = matrix[col][row]; 
    int regionSize = 0; 
    while (! toVisit.isEmpty()) { 
     Point p = toVisit.removeFirst(); // use removeLast() to emulate DFS 
     if (! visited.contains(p)) { 
     regionSize ++; 
     visited.add(p); 
     // now, add its neighbors 
     for (int[] d : new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}) { 
      int nx = p.x + d[0]; 
      int ny = p.y + d[1]; 
      if (nx >= 0 && nx < matrix[0].length 
       && ny >= 0 && ny < matrix.length 
       && matrix[ny][nx] == regionColor) { 
       toVisit.addLast(new Point(nx, ny)); // add neighbor 
      } 
     } 
     } 
    } 
    return regionSize; 
} 

注意。再帰DFSでは、プログラムスタックを使用して、明示的なスタック/デキューの先頭にあるtoVisitを追跡します。アルゴリズムの進行状況を追跡するためにSystem.out.printlnを追加することでこれをテストできます。

以上、boolean[][]アレイの代わりにPointのHashSetを使用していますが、どちらを使うのが最も簡単です。