(SPOJ) Batalha Naval - Solution

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

The solution below used Breadth-First Search to solve this problem. It first check how many ships there are in the map. Then, every ship has its characters replaced by its number identification. It allows us to know how many ships remain in the end.


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

class Main {
    public int[][] matrix;
    public boolean[][] visited;
    public int[] vi = {-1,0,0,1};
    public int[] vj = {0,-1,1,0};
    public int numRows;
    public int numCols;
    public int numShips;
   
    public void bfs(int currI, int currJ) {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        queue.add(new Coord(currI, currJ));
       
        while (queue.size() > 0) {
            Coord curr = queue.poll();
            int cI = curr.i;
            int cJ = curr.j;
           
            if (visited[cI][cJ]) {
                continue;
            }
            visited[cI][cJ] = true;
            matrix[cI][cJ] = numShips;

            for (int i = 0; i < 4; i++) {
                int nextI = cI+vi[i];
                int nextJ = cJ+vj[i];
                if (nextI <= 0 || nextJ <= 0 || nextI > numRows || nextJ > numCols || matrix[nextI][nextJ] == -1) {
                    continue;
                }
                queue.add(new Coord(nextI, nextJ));
            }
        }
    }
   
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        String line = br.readLine();
        String[] s = line.split(" ");
        numRows = Integer.parseInt(s[0]);
        numCols = Integer.parseInt(s[1]);

        matrix = new int[numRows+1][numCols+1];
        for (int i = 1; i <= numRows; i++) {
            line = br.readLine();
            for (int j = 1; j <= numCols; j++) {
                if (line.charAt(j-1) == '.') {
                    matrix[i][j] = -1;
                }
                else {
                    matrix[i][j] = 0;
                }
            }
        }
            
        // find out number of ships
        numShips = 1;
        visited = new boolean[numRows+1][numCols+1];
        for (int i = 1; i <= numRows; i++) {
            for (int j = 1; j <= numCols; j++) {
                if (matrix[i][j] == 0 && !visited[i][j]) {
                    bfs(i, j);
                    numShips++;               
                }
            }
        }

        line = br.readLine();
        int numAttacks = Integer.parseInt(line);
        for (int i = 0; i < numAttacks; i++) {
            line = br.readLine();
            s = line.split(" ");
            matrix[Integer.parseInt(s[0])][Integer.parseInt(s[1])] = -1;
        }
       
        HashSet<Integer> ships = new HashSet<>();
        for (int i = 1; i <= numRows; i++) {
            for (int j = 1; j <= numCols; j++) {
                if (matrix[i][j] == -1) {
                    continue;               
                }
                ships.add(matrix[i][j]);         
            }
        }
       
        bw.write((numShips-1-ships.size())+"\n");
       
        bw.flush();
        bw.close();
                          
        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;
    }
}