(UVA) Grid Colouring - Solution

I used Depth-First Search to solve this problem.

First, I find the character that is responsible for the contour. Then, I iterate over the borders of the matrix in order to visit all the spaces that are not completely surrounded by the contour characters. After it is done, I apply the DFS method every time I find a marking character.

Moreover, I had to use BufferedWriter instead of the common System.out to print the answers because I got a "Time Limit Exceeded" when I used the second option.


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

class Main  {
    public static final int ROWS = 30;
    public static final int COLS = 80;
    public static int numCols;
    public static int numRows;
    public static char[][] matrix;
    public static boolean[][] visited;
    public static char contour;
    public static char marking;
    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 (currX < 0 || currX >= numRows || currY < 0 || currY >= numCols || matrix[currX][currY] == contour || visited[currX][currY]) {
            return;
        }
       
        visited[currX][currY] = true;
        matrix[currX][currY] = marking;
        for (int i = 0; i < 4; i++) {
            int nextX = currX+vx[i];
            int nextY = currY+vy[i];
            dfs(nextX, nextY);
        }
    }
   
    public static void dfsSpace(int currX, int currY) {
        if (currX < 0 || currX >= numRows || currY < 0 || currY >= numCols || (matrix[currX][currY] != ' ' && matrix[currX][currY] != 0) || 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];
            dfsSpace(nextX, nextY);
        }
    }
   
    public static 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();
        while (line != null) {
            matrix = new char[ROWS][COLS];
           
            numRows = 0;
            numCols = 0;
            while (line.length() > 0 && line.charAt(0) != '_') {
                for (int i = 0; i < line.length(); i++) {
                    matrix[numRows][i] = line.charAt(i);
                }
                if (line.length() > numCols) {
                    numCols = line.length();
                }
                numRows++;
                line = br.readLine();
            }
            String limit = line;
           
            boolean foundContour = false;
            for (int i = 0; i < numRows && !foundContour; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (matrix[i][j] != ' ' && matrix[i][j] != 0) {
                        contour = matrix[i][j];
                        foundContour = true;
                        break;
                    }
                }
            }
           
            visited = new boolean[ROWS][COLS];
            for (int i = 0; i < numRows; i++) {
                dfsSpace(i, 0);
            }
            for (int i = 0; i < numRows; i++) {
                dfsSpace(i, numCols-1);
            }
            for (int i = 0; i < numCols; i++) {
                dfsSpace(0, i);
            }
            for (int i = 0; i < numCols; i++) {
                dfsSpace(numRows-1, i);
            }
           
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (matrix[i][j] != ' ' && matrix[i][j] != 0 && matrix[i][j] != contour) {
                        marking = matrix[i][j];
                        dfs(i, j);
                    }
                }
            }
           
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (matrix[i][j] != 0) {
                        bw.write(matrix[i][j]);
                    }
                }
                bw.write("\n");
            }
           
            bw.write(limit + "\n");
            line = br.readLine();
        }
       
        bw.flush();
        bw.close();
               
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}