# 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 {

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.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;
}

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;
}

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

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

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

}

// 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);
}
}
``````