(UVA) Basic Wall Maze - Solution

I used Breadth-First Search to solve this problem.


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

class Main  {
    public static int[] vi = {-1,1,0,0};
    public static int[] vj = {0,0,-1,1};
    public static char[] p = {'N','S','W','E'};
   
    public static boolean checkWalls(int currPosRow, int currPosCol, int nextRow, int nextCol, Coord[] walls, int way) {
        // moving vertically
        if (way == 0 || way == 1) {
            for (int i = 0; i < 3; i++) {
                // I want a horizontal wall
                for (int j = walls[i].startCol+1; j <= walls[i].endCol; j++) {
                    if (currPosCol == j && ((currPosRow == walls[i].startRow && nextRow == walls[i].startRow+1) || (currPosRow == walls[i].startRow+1 && nextRow == walls[i].startRow))) {
                        return false;
                    }
                }
            }
        }
        // moving horizontally
        else if (way == 2 || way == 3) {
            for (int i = 0; i < 3; i++) {
                for (int j = walls[i].startRow+1; j <= walls[i].endRow; j++) {
                    if (currPosRow == j && ((currPosCol == walls[i].startCol && nextCol == walls[i].startCol+1) || (currPosCol == walls[i].startCol+1 && nextCol == walls[i].startCol))) {
                        return false;
                    }
                }
            }
        }
       
        return true;
    }
   
    public static String bfs(CoordPos s, CoordPos e, Coord[] walls) {
        Queue<CoordPos> queue = new ArrayDeque<CoordPos>();
        queue.add(s);
       
        Queue<String> path = new ArrayDeque<String>();
        path.add("");
       
        int[][] addedToQueue = new int[7][7];
        addedToQueue[s.row][s.col] = 1;
       
        while (queue.size() > 0) {
            CoordPos currPos = queue.poll();
            int currPosRow = currPos.row;
            int currPosCol = currPos.col;
            String currPath = path.poll();
            if (currPosRow == e.row && currPosCol == e.col) {
                return currPath;
            }
           
            for (int i = 0; i < 4; i++) {
                int nextRow = currPosRow+vi[i];
                int nextCol = currPosCol+vj[i];
                if (nextRow >= 1 && nextCol >= 1 && nextRow < 7 && nextCol < 7 && addedToQueue[nextRow][nextCol] == 0 && checkWalls(currPosRow, currPosCol, nextRow, nextCol, walls, i)) {
                    CoordPos cp = new CoordPos(nextRow, nextCol);
                    queue.add(cp);
                   
                    path.add(currPath+p[i]);
                    addedToQueue[nextRow][nextCol] = 1;
                }
            }
        }
       
        return "";
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
      
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            } 
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp;     
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int startCol = reader(br);
        int startRow = reader(br);
        while (startCol != 0 && startRow != 0) {
            CoordPos s = new CoordPos(startRow, startCol);
           
            int endCol = reader(br);
            int endRow = reader(br);
            CoordPos e = new CoordPos(endRow, endCol);
           
            Coord[] walls = new Coord[3];
            for (int i = 0; i < 3; i++) {
                int startCol2 = reader(br);
                int startRow2 = reader(br);
                int endCol2 = reader(br);
                int endRow2 = reader(br);
                walls[i] = new Coord(startRow2, startCol2, endRow2, endCol2);
            }
           
            System.out.println(bfs(s, e, walls));
           
            startCol = reader(br);
            startRow = reader(br);
        }
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

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

class Coord {
    int startRow;
    int startCol;
    int endRow;
    int endCol;
   
    public Coord(int startRow, int startCol, int endRow, int endCol) {
        this.startRow = startRow;
        this.endRow = endRow;
        this.startCol = startCol;
        this.endCol = endCol;
    }
}