(SPOJ) Colorindo - Solution

Link to the problem: http://br.spoj.com/problems/COLOR11/

This problem wants us to find the amount of squares that a child can paint using only a color. One way of solving this problem is using Flood Fill, an algorithm that finds all the squares of the matrix that are connected to the initial square. The solution below is using a non-recursive implementation (Breath-First Search) to find the answer.


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

class Main {
    public int numRows;
    public int numCols;
    public int[][] matrix;
    public boolean[][] visited;
    public int count;
    public int[] vi = {-1,-1,-1,0,0,1,1,1};
    public int[] vj = {-1,0,1,-1,1,-1,0,1};
   
    public void bfs(int currI, int currJ) {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        queue.add(new Coord(currI, currJ));
       
        while (queue.size() > 0) {
            Coord c = queue.poll();
            int i = c.i;
            int j = c.j;
           
            if (visited[i][j]) {
                continue;
            }
            visited[i][j] = true;
       
            count++;
            for (int k = 0; k < 8; k++) {
                int nextI = i+vi[k];
                int nextJ = j+vj[k];
                if (nextI <= 0 || nextJ <= 0 || nextI > numRows || nextJ > numCols || visited[nextI][nextJ]) {
                    continue;
                }
                queue.add(new Coord(nextI, nextJ));
            }
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        String[] s = line.split("\\s");
        numRows = Integer.parseInt(s[0]);
        numCols = Integer.parseInt(s[1]);
        int startX = Integer.parseInt(s[2]);
        int startY = Integer.parseInt(s[3]);
        int numInvalid = Integer.parseInt(s[4]);
       
        matrix = new int[numRows+1][numCols+1];
        for (int i = 0; i < numInvalid; i++) {
            line = br.readLine();
            s = line.split("\\s");
            int x = Integer.parseInt(s[0]);
            int y = Integer.parseInt(s[1]);
            visited[x][y] = true;
        }
       
        count = 0;
        visited = new boolean[numRows+1][numCols+1];
        bfs(startX, startY);
       
        System.out.println(count);
       
        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;
    }
}