Kattis Challenge "Grid"

  1import java.io.BufferedReader;
  2import java.io.IOException;
  3import java.io.InputStreamReader;
  4import java.util.LinkedList;
  5import java.util.Queue;
  6class Kattis_Grid {
  7    public static void main(String[] args) throws IOException {
  8        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  9        String[] temp = br.readLine().split(" ");
 10        int rows = Integer.parseInt(temp[0]);
 11        int cols = Integer.parseInt(temp[1]);
 12        /*
 13        This program uses 1D arrays instead of 2D arrays to enhance 
 14        performance at the cost of readability. This entire program will be
 15        micro-optimized to death.
 16         */
 17        int[] distance = new int[rows * cols];
 18        int[] grid = new int[rows * cols];
 19        /*
 20        Read a line as a String and store it as a character array. Subtracting 
 21        48 from the ASCII representation of a number will give you its decimal 
 22        value. This nested loop also sets the entire distance array to -1 to 
 23        represent that cell of the grid as being unvisited.
 24         */
 25        for (int x = 0; x < rows; x++) {
 26            char[] temp2 = br.readLine().toCharArray();
 27            for (int y = 0; y < cols; y++) {
 28                grid[y + cols * x] = (temp2[y] - 48);
 29                distance[y + cols * x] = -1;
 30            }
 31        }
 32        //This is the starting point.
 33        distance[0] = 0;
 34        /*
 35        The non-recursive implementation of BFS uses a queue (First In First Out)
 36        instead of a stack (First In Last Out). It checks whether a Node has 
 37        been discovered before enqueueing the Node rather than delaying this 
 38        check until the Node is dequeued from the queue.
 39         */
 40        Queue<int[]> queue = new LinkedList<>();
 41        /*
 42        I'm using a two-digit integer array in lieu of a "Node" object to shave 
 43        off some run time.
 44         */
 45        queue.add(new int[]{0, 0});
 46        int x, y, newX, newY;
 47        int[] current;
 48        while (!queue.isEmpty()) {
 49            //As we leave a Node we dequeue it.
 50            current = queue.remove();
 51            x = current[0];
 52            y = current[1];
 53            //Micro-optimization that saves the program one needless loop.
 54            if (x == rows - 1 && y == cols - 1) {
 55                break;
 56            }
 57            int direction = 0;
 58            //Check every cardinal direction.
 59            while (direction++ < 4) {
 60                switch (direction) {
 61                    //Up
 62                    case 1:
 63                        newX = x;
 64                        newY = y + grid[x * cols + y] * -1;
 65                        break;
 66                    //Down
 67                    case 2:
 68                        newX = x;
 69                        newY = y + grid[x * cols + y] * 1;
 70                        break;
 71                    //Left
 72                    case 3:
 73                        newX = x + grid[x * cols + y] * -1;
 74                        newY = y;
 75                        break;
 76                    //Right
 77                    case 4:
 78                        newX = x + grid[x * cols + y] * 1;
 79                        newY = y;
 80                        break;
 81                    default:
 82                        newX = 0;
 83                        newY = 0;
 84                        break;
 85                }
 86                /*
 87                Check if the direction you've moved in is within the bounds
 88                of the grid. If the node is within bounds,
 89                 */
 90                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
 91                    // and the node is unvisited,
 92                    if (distance[newX * cols + newY] == -1) {
 93                        // add it to the queue and update the distance matrix.
 94                        queue.add(new int[]{newX, newY});
 95                        distance[newX * cols + newY] = distance[x * cols + y] + 1;
 96                    }
 97                }
 98            }
 99        }
100        /*
101        Print the distance value of the bottom-right cell because that is the
102        final destination in this problem.
103         */
104        System.out.print(distance[(rows - 1) * cols + (cols - 1)]);
105    }
106}