使用 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

如果您在维基百科页面上的伪代码部分下查看深度优先搜索，他们有一个DFS算法迭代验证的示例。应该能够从那里找出解决方案。

*编辑

要使其迭代，您可以执行以下操作：

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>();

如果要使用 BFS 而不是 DFS，只需将堆栈更改为队列，即可获得所需的结果。此链接对堆栈和队列进行了很好的解释，并且在您了解该主题时可能会很有用。

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来跟踪算法的进度来测试这一点。

上面，我使用Point的 HashSet 而不是boolean[][]数组，但请随意使用对您来说最简单的方法。