Finding biggest area of adjacent numbers in a matrix using DFS algorithm

Question

I am learning programming on my own with a book for beginners. My last task after chapter Arrays is to :

 // 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}

As a hint I have - use DFS or BFS algorithm. After I read about them and saw many their implementations I got the idea but it was just too overwhelming for a beginner. I found the solution for my task and after I runned the program many times I understood how it works and now I can solve the problem on my own. Although, I am happy that this solution helped me to learn about recursion, I am wondering can the following code be modified in iterative way and if so can you give me hints how to do it? Thank you in advance.

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

If you look on the Wikipedia page for Depth-first search under the pseudocode section, they have an example of a iterative verision of the DFS algorithm. Should be able to figure out a solution from there.

*Edit

To make it iterative, you can do the following:

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

Everytime you would call the dfs() method in the recursive method, you should be calling S.push(). You can create class Position as follows

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

and use the built in java class java.util.Stack to make it easy.

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

If you want to use BFS instead of DFS, you can simple change the Stack to a Queue and you will get the desired result. This link has a very nice explanation of stacks and queues and may prove useful as you learn about the topic.

Answer 2

I assume you are looking for a BFS solution, since you already have a working DFS, and BFS is iterative while DFS is recursive (or at least, is easier to implement recursively).

The (untested) BFS code to measure a region's size could be:

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;
}

Note that you can change a (queue-based) BFS into an iterative DFS by changing a single line. In a recursive DFS, you would be using the program stack to keep track of toVisit intead of an explicit stack/deque. You can test this by adding a System.out.println to track the algorithm's progress.

Above, I use a HashSet of Point instead of a boolean[][] array, but feel free to use whichever is easiest for you.