(UVA) Continents - Solution

I used Depth-First Search to solve this problem.


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

class Main  {
    public static char[][] matrix;
    public static boolean[][] visited; 
    public static char c; 
    public static int count;
    public static int rows;
    public static int cols;
    public static int[] vx = {-1,0,0,1};
    public static int[] vy = {0,-1,1,0};

    public static void dfs(int currX, int currY) {
        if (currY < 0) {
            currY = cols+currY;
        }
        if (currY >= cols) {
            currY = currY-cols;
        }
        if (currX < 0 || currX >= rows || visited[currX][currY] || matrix[currX][currY] != c) {
            return;
        }
       
        count++;
        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();
        while (line != null) {
            String[] s = line.split("\\s");
            rows = Integer.parseInt(s[0]);
            cols = Integer.parseInt(s[1]);
           
            matrix = new char[rows][cols];
            visited = new boolean[rows][cols];
            for (int i = 0; i < rows; i++) {
                line = br.readLine();
                for (int j = 0; j < cols; j++) {
                    matrix[i][j] = line.charAt(j);
                }
            }
           
            line = br.readLine();
            s = line.split("\\s");
            int posXMijid = Integer.parseInt(s[0]);
            int posYMijid = Integer.parseInt(s[1]);
            c = matrix[posXMijid][posYMijid];
            count = 0;
            dfs(posXMijid, posYMijid);
           
            int max = -1;
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    count = 0;
                    dfs(i, j);
                    if (count > max) {
                        max = count;
                    }
                }
            }
           
            System.out.println(max);
           
            line = br.readLine();
            if (line == null) {
                break;
            }
            line = br.readLine();
        }
               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução