(UVA) Battleships - Solution

I used Depth-First Search to solve this problem.


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

class Main {
    public static char[][] grid;
    public static boolean[][] visited;
    public static int[] vx = {0,-1,0,1};
    public static int[] vy = {-1,0,1,0};
    public static int gridSize;
    public static int countShip;
   
    public static void dfs(int currX, int currY) {
        if (currX < 0 || currY < 0 || currX >= gridSize || currY >= gridSize || grid[currX][currY] == '.' || visited[currX][currY]) {
            return;
        }
       
        visited[currX][currY] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = currX+vx[i];
            int nextY = currY+vy[i];
            dfs(nextX, nextY);
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        int numTests = Integer.parseInt(line);
        for (int i = 0; i < numTests; i++) {
            line = br.readLine();
            gridSize = Integer.parseInt(line);
            grid = new char[gridSize][gridSize];
            for (int j = 0; j < gridSize; j++) {
                line = br.readLine();
                for (int k = 0; k < gridSize; k++) {
                    grid[j][k] = line.charAt(k);
                }
            }
           
            countShip = 0;
            visited = new boolean[gridSize][gridSize];
            for (int j = 0; j < gridSize; j++) {
                for (int k = 0; k < gridSize; k++) {
                    if (grid[j][k] == 'x' && !visited[j][k]) {
                        dfs(j, k);
                        countShip++;
                    }
                }
            }
           
            System.out.println("Case " + (i+1) + ": " + countShip);
        }
                                             
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}