(UVA) The path in the colored field - Solution

Breadth-First Search was used to solve this problem.


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

class Main {
    public static int[][] matrix;
    public static boolean[][] visited;
    public static int[] vi = {-1,0,0,1};
    public static int[] vj = {0,-1,1,0};
   
    public static int bfs(int row, int col, int size) {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        queue.add(new Coord(row, col, 0));
       
        while (queue.size() > 0) {
            Coord curr = queue.poll();
            int currRow = curr.row;
            int currCol = curr.col;
            int currSteps = curr.steps;
           
            if (visited[currRow][currCol]) {
                continue;
            }
            visited[currRow][currCol] = true;
           
            if (matrix[currRow][currCol] == 3) {
                return currSteps;
            }
           
            for (int i = 0; i < 4; i++) {
                int nextRow = currRow+vi[i];
                int nextCol = currCol+vj[i];
                if (nextRow < 0 || nextCol < 0 || nextRow >= size || nextCol >= size) {
                    continue;
                }
                queue.add(new Coord(nextRow, nextCol, currSteps+1));
            }
        }
       
        return -1;
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        String line = br.readLine();
        while (line != null) {
            int size = Integer.parseInt(line);
        
            matrix = new int[size][size];
            for (int i = 0; i < size; i++) {
                line = br.readLine();
                for (int j = 0; j < size; j++) {
                    matrix[i][j] = Integer.parseInt(line.charAt(j)+"");
                }
            }
              
            int max = -1;
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    if (matrix[i][j] == 1) {
                        visited = new boolean[size][size];
                        int steps = bfs(i, j, size);
                        if (steps > max) {
                            max = steps;
                        }
                    }
                }
            }
           
            System.out.println(max);
           
            line = br.readLine();
        }   
              
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    int row;
    int col;
    int steps;
   
    public Coord(int row, int col, int steps) {
        this.row = row;
        this.col = col;
        this.steps = steps;
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução