(UVA) The Seasonal War - Solution 3

This solution is using Depth-First Search.

If you want to see other solutions for this problem, click here and here. Both of them are using Breadth-First Search.


import java.io.*;
import java.util.*;

class Main  {
    public static int[][] m;
    public static int[][] visited;
   
    public static void dfs(int squareDimension, int i, int j) {
        if (i < 0 || j < 0 || i >= squareDimension || j >= squareDimension || visited[i][j] == 1 || m[i][j] == 0s) {
          return;
        }
       
        int[] vi = {-1,-1,-1,0,0,1,1,1};
        int[] vj = {-1,0,1,-1,1,-1,0,1};
       
        visited[i][j] = 1;
       
        for (int k = 0; k < 8; k++) {
            int nextI = i+vi[k];
            int nextJ = j+vj[k];
            dfs(squareDimension, nextI, nextJ);
        }
       
        return;
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
       
        String line;
        while ((line = br.readLine()) != null) {
            int squareDimension = Integer.parseInt(line);
           
            // read matrix
            m = new int[squareDimension][squareDimension];
            for (int i = 0; i < squareDimension; i++) {
                line = br.readLine();
                for (int j = 0; j < squareDimension; j++) {
                    m[i][j] = line.charAt(j)-'0';
                }
            }
           
            // count war eagles
            int count = 0;
            visited = new int[squareDimension][squareDimension];
            for (int i = 0; i < squareDimension; i++) {
                for (int j = 0; j < squareDimension; j++) {
                    if (visited[i][j] == 0 && m[i][j] == 1) {
                        dfs(squareDimension, i, j);
                        count++;
                    }
                }
            }
           
            System.out.println("Image number " + ++numCase + " contains " + count + " war eagles.");
        }
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}