(UVA) The Seasonal War - Solution 1

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

class Main  {
    public static HashSet<Integer> visited = new HashSet<Integer>();
   
    public static void bfs(int startPosI, int startPosJ, int squareDimension, int[] array) {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        Coord c = new Coord(startPosI, startPosJ);
        queue.add(c);
       
        int[] vi = {-1,-1,-1,0,0,1,1,1};
        int[] vj = {-1,0,1,-1,1,-1,0,1};
       
        while (queue.size() > 0) {
            Coord tmp = queue.poll();
            int currPosI = tmp.i;
            int currPosJ = tmp.j;
           
            visited.add((currPosI*squareDimension)+currPosJ);
           
            for (int i = 0; i < 8; i++) {
                int nextPosI = vi[i]+currPosI;
                int nextPosJ = vj[i]+currPosJ;
                if (nextPosI >= 0 && nextPosJ >= 0 && nextPosI < squareDimension && nextPosJ < squareDimension && array[(nextPosI*squareDimension)+nextPosJ] == 1 && !visited.contains((nextPosI*squareDimension)+nextPosJ)) {
                    c = new Coord(nextPosI, nextPosJ);
                    queue.add(c);
                }
            }
        }
    }

    public static int checkComponents(int[][] m, int[] array, int squareDimension) {
        int components = 0;
        for (int i = 0; i < squareDimension; i++) {
            for (int j = 0; j < squareDimension; j++) {
                if (m[i][j] == 1 && !visited.contains(i*squareDimension+j)) {
                    bfs(i, j, squareDimension, array);                       
                    components++;
                }
            }
        }
       
        return components;
    }
   
    public static void transferMToArray(int[][] m, int[] array, int squareDimension) {
        for (int i = 0; i < squareDimension; i++) {
            for (int j = 0; j < squareDimension; j++) {
                array[(i*squareDimension)+j] = m[i][j];
            }
        }
    }
   
    public static void readMatrix(BufferedReader br, int[][] m, int squareDimension) throws NumberFormatException, IOException {
        for (int i = 0; i < squareDimension; i++) {
            String matrixLine = br.readLine();
            for (int j = 0; j < matrixLine.length(); j++) {
                m[i][j] = matrixLine.charAt(j)-'0';
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int testCase = 0;
        String line = br.readLine();
        while (line != null) {
            int squareDimension = Integer.parseInt(line);
            int[][] m = new int[squareDimension][squareDimension];
            readMatrix(br, m, squareDimension);

            int[] array = new int[squareDimension*squareDimension];
            transferMToArray(m, array, squareDimension);

            int components = checkComponents(m, array, squareDimension);
           
            System.out.println("Image number " + (++testCase) + " contains " + components + " war eagles.");
           
            visited.clear();
            line = br.readLine();
        }
               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    int i;
    int j;
   
    public Coord(int i, int j) {
        this.i = i;
        this.j = j;
    }
}