Skip to content
Archive

Kattis Challenge "Grid"

Solved using a non-recursive version of BFS. Runs in pretty good time.

Kattis Challenge "Grid"

Solved using a non-recursive version of BFS. Runs in pretty good time.

Problem

My Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Kattis_Grid {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        int rows = Integer.parseInt(temp[0]);
        int cols = Integer.parseInt(temp[1]);
        /*
        This program uses 1D arrays instead of 2D arrays to enhance 
        performance at the cost of readability. This entire program will be
        micro-optimized to death.
         */
        int[] distance = new int[rows * cols];
        int[] grid = new int[rows * cols];
        /*
        Read a line as a String and store it as a character array. Subtracting 
        48 from the ASCII representation of a number will give you its decimal 
        value. This nested loop also sets the entire distance array to -1 to 
        represent that cell of the grid as being unvisited.
         */
        for (int x = 0; x < rows; x++) {
            char[] temp2 = br.readLine().toCharArray();
            for (int y = 0; y < cols; y++) {
                grid[y + cols * x] = (temp2[y] - 48);
                distance[y + cols * x] = -1;
            }
        }
        //This is the starting point.
        distance[0] = 0;
        /*
        The non-recursive implementation of BFS uses a queue (First In First Out)
        instead of a stack (First In Last Out). It checks whether a Node has 
        been discovered before enqueueing the Node rather than delaying this 
        check until the Node is dequeued from the queue.
         */
        Queue<int[]> queue = new LinkedList<>();
        /*
        I'm using a two-digit integer array in lieu of a "Node" object to shave 
        off some run time.
         */
        queue.add(new int[]{0, 0});
        int x, y, newX, newY;
        int[] current;
        while (!queue.isEmpty()) {
            //As we leave a Node we dequeue it.
            current = queue.remove();
            x = current[0];
            y = current[1];
            //Micro-optimization that saves the program one needless loop.
            if (x == rows - 1 && y == cols - 1) {
                break;
            }
            int direction = 0;
            //Check every cardinal direction.
            while (direction++ < 4) {
                switch (direction) {
                    //Up
                    case 1:
                        newX = x;
                        newY = y + grid[x * cols + y] * -1;
                        break;
                    //Down
                    case 2:
                        newX = x;
                        newY = y + grid[x * cols + y] * 1;
                        break;
                    //Left
                    case 3:
                        newX = x + grid[x * cols + y] * -1;
                        newY = y;
                        break;
                    //Right
                    case 4:
                        newX = x + grid[x * cols + y] * 1;
                        newY = y;
                        break;
                    default:
                        newX = 0;
                        newY = 0;
                        break;
                }
                /*
                Check if the direction you've moved in is within the bounds
                of the grid. If the node is within bounds,
                 */
                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols) {
                    // and the node is unvisited,
                    if (distance[newX * cols + newY] == -1) {
                        // add it to the queue and update the distance matrix.
                        queue.add(new int[]{newX, newY});
                        distance[newX * cols + newY] = distance[x * cols + y] + 1;
                    }
                }
            }
        }
        /*
        Print the distance value of the bottom-right cell because that is the
        final destination in this problem.
         */
        System.out.print(distance[(rows - 1) * cols + (cols - 1)]);
    }
}

Related Reading

Related entries

Selected from shared tags, categories, and nearby entries in the same section.

Relationship Map

Connected Memory

This relationship map centers on the current entry and highlights connected categories and tags.

Categories 0
Tags 0
Entries 0