Minimum Steps for Boundary (Tiles)

Problem:

Suppose there is a colored marble floor in block format which has 2 colors:

1. White
2. Orange

You have been asked to stand on any specific block, and you can travel through adjacent (left, right, up & down) white blocks only.

Write a program to find the length of the minimum steps to reach one of the boundaries of the floor without stepping on an orange block.

Sample input:

1. 0 represents white, and 1 represents orange
2. Sample input: int arr[][] = {{1, 1, 1, 0, 1}, {1, 0, 0, 0, 1}, {0, 0, 1, 0, 1}, {1, 0, 1, 1, 0}}
3. In the above diagram you need min 2 steps to reach a boundary i.e {1, 2} (starting position) -> {1, 3} -> {0, 3}

Write the following method:

public int minStepsForBoundary(int n, int m, int[][] arr) {

// write code here

}

Solution:

We create a Node 2D-array with the same dimensions as the input arr. We initialize the "visited" variable to true for the 1 blocks (orange) so we don't visit them. We run Breadth-First Search (BFS) starting at (n, m) and stop when all nodes are visited or we reach a wall (boundary).

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Node {
    int x, y;
    boolean visited;
    Node from;

    Node(int x, int y) {
        this.x = x;
        this.y = y;
        this.visited = false;
        this.from = null;
    }
}

public class MainClass {

    /*  Breadth-First Search (BFS) in 2D Matrix/2D-Array (https://algorithms.tutorialhorizon.com/breadth-first-search-bfs-in-2d-matrix-2d-array/)
        if has path:
            return number of steps
        otherwise:
            return -1
     */
    public int minStepsForBoundary(int n, int m, int[][] arr) {

        int h = arr.length;
        if (h == 0)
            return -1;
        int l = arr[0].length;

        Node[][] nodeMat = new Node[h][l];
        for (int x = 0; x < h; x++) {
            for (int y = 0; y < l; y++) {
                nodeMat[x][y] = new Node(x, y);
                nodeMat[x][y].visited = arr[x][y] == 1; // cant visit if 1 (wall)
            }
        }

        // check if init coordinate is legal
        if (n < 0 || m < 0 || n >= h || m >= l) {
            return -1;
        }

        Queue<Node> queue = new LinkedList<>();

        queue.add(nodeMat[n][m]);
        Node wallNode = null;

        while (!queue.isEmpty()) {

            Node coordinate = queue.remove();
            int row = coordinate.x;
            int col = coordinate.y;

            if (nodeMat[row][col].visited)
                continue;

            // check if wall
            if (row == 0 || row + 1 == h || col == 0 || col + 1 == l) {
                wallNode = coordinate;
                break;
            }

            nodeMat[row][col].visited = true;

            if (!nodeMat[row][col - 1].visited) {
                // go left
                nodeMat[row][col - 1].from = coordinate;
                queue.add(nodeMat[row][col - 1]);
            }

            if (!nodeMat[row][col + 1].visited) {
                // go right
                nodeMat[row][col + 1].from = coordinate;
                queue.add(nodeMat[row][col + 1]);
            }

            if (!nodeMat[row - 1][col].visited) {
                // go up
                nodeMat[row - 1][col].from = coordinate;
                queue.add(nodeMat[row - 1][col]);
            }

            if (!nodeMat[row + 1][col].visited) {
                // go down
                nodeMat[row + 1][col].from = coordinate;
                queue.add(nodeMat[row + 1][col]);
            }

        }

        // finished BFS, now print the path (not required)
        if (wallNode != null) {
            Stack<Node> pathStack = new Stack<>();

            while (wallNode != null) {
                pathStack.push(wallNode);
                wallNode = wallNode.from;
            }

            int size = pathStack.size();

            while (!pathStack.empty()) {
                Node n1 = pathStack.pop();
                System.out.print("{" + n1.x + ", " + n1.y + "} ");
            }
            System.out.println();

            return size - 1; //  don't count initial node
        }

        // -1 since no path
        return -1;

    }

    public static void main(String[] args) {

        int[][] grid = new int[][]{
                {1, 1, 1, 0, 1},
                {1, 0, 0, 0, 1},
                {0, 0, 1, 0, 1},
                {1, 0, 1, 1, 0}
        };
        MainClass d = new MainClass();
        int steps = d.minStepsForBoundary(1, 2, grid);
        System.out.println(steps);

        steps = d.minStepsForBoundary(3, 1, grid);
        System.out.println(steps);
    }
}