查找最大使用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下的伪代码段，他们有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

我假定你正在寻找一个BFS的解决方案，因为你已经有一个工作DFS和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; 
} 

请注意，您可以更改（基于队列）通过改变单行BFS到迭代DFS。在递归的DFS，你会使用程序堆栈跟踪toVisit这一翻译明确的堆栈/双端队列的。您可以通过添加一个System.out.println来测试这个算法的进度。

以上我使用的是HashSet的Point而不是boolean[][]数组，但可以随意使用哪一个最容易适合您。