Amazon Interview Question SDE-2s
Team: Media Experience Team
Country: India
Interview Type: In-Person
static void Main(string[] args)
{
char[][] matrix = new char[][] { new char[] {'1', '1', '1', '1', '1'},
new char[] {'S', '1', 'X', '1', '1'},
new char[] {'1', '1', '1', '1', '1'},
new char[] {'X', '1', '1', 'E', '1'},
new char[] {'1', '1', '1', '1', 'X'} };
var path = FindShortestPath(matrix, 5, 5, new Point(1, 0), new Point(3, 3));
Console.ReadKey();
}
public class Point
{
public int x;
public int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
}
public static List<Point> FindShortestPath(char[][] matrix, int rows, int cols, Point s, Point e)
{
bool[,] visited = new bool[rows, cols];
Point[,] parent = new Point[rows, cols];
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
{
visited[i, j] = false;
parent[i, j] = null;
}
List<Point> path = new List<Point>();
int pathLength = Int32.MaxValue;
Queue q = new Queue();
q.Enqueue(s);
while (q.Count != 0)
{
Point curr = (Point) q.Dequeue();
visited[curr.x, curr.y] = true;
//Console.Write("({0}, {1}) ", curr.x, curr.y);
if (curr.x == e.x && curr.y == e.y)
{
List<Point> currPath = new List<Point>();
while (parent[curr.x, curr.y] != s)
{
curr = parent[curr.x, curr.y];
currPath.Add(curr);
Console.Write("({0}, {1}) ", curr.x, curr.y);
}
Console.WriteLine();
if (currPath.Count < pathLength)
{
path.Clear();
path.AddRange(currPath);
}
}
if (curr.y + 1 < cols && matrix[curr.x][curr.y + 1] != 'X' && !visited[curr.x, curr.y + 1])
{
q.Enqueue(new Point(curr.x, curr.y + 1));
parent[curr.x, curr.y + 1] = curr;
}
if (curr.y - 1 >= 0 && matrix[curr.x][curr.y - 1] != 'X' && !visited[curr.x, curr.y - 1])
{
q.Enqueue(new Point(curr.x, curr.y - 1));
parent[curr.x, curr.y - 1] = curr;
}
if (curr.x - 1 >= 0 && matrix[curr.x - 1][curr.y] != 'X' && !visited[curr.x - 1, curr.y])
{
q.Enqueue(new Point(curr.x - 1, curr.y));
parent[curr.x - 1, curr.y] = curr;
}
if (curr.x + 1 < rows && matrix[curr.x + 1][curr.y] != 'X' && !visited[curr.x + 1, curr.y])
{
q.Enqueue(new Point(curr.x + 1, curr.y));
parent[curr.x + 1, curr.y] = curr;
}
}
return path;
}
Java implementation
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class ShortestPath {
private static class Position {
public int x;
public int y;
public Position predecessor;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
public Position(int x, int y, Position predecessor) {
this(x, y);
this.predecessor = predecessor;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Position other = (Position) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}
@Override
public String toString() {
return "[" + x + "," + y + "]";
}
}
private char[][] matrix;
private Position[] shortestPath;
private Stack<Position> path;
private Position start;
public ShortestPath(char[][] matrix) {
this.matrix = matrix;
}
public Position[] getPathDFS() {
findStart();
path = new Stack<Position>();
shortestPath = null;
if (start != null) {
next(start);
}
return shortestPath;
}
public Position[] getPathBFS() {
findStart();
path = new Stack<Position>();
shortestPath = null;
LinkedList<Position> predecessors = new LinkedList<Position>();
Queue<Position> queue = new LinkedList<Position>();
queue.offer(start);
visit(start);
if (start == null) {
return null;
}
while (!queue.isEmpty()) {
Position position = queue.poll();
predecessors.add(position);
if (!endFound(position)) {
Position nextPosition = new Position(position.x + 1, position.y, position);
if (isVisitable(nextPosition)) {
queue.offer(nextPosition);
visit(nextPosition);
}
nextPosition = new Position(position.x, position.y + 1, position);
if (isVisitable(nextPosition)) {
queue.offer(nextPosition);
visit(nextPosition);
}
nextPosition = new Position(position.x - 1, position.y, position);
if (isVisitable(nextPosition)) {
queue.offer(nextPosition);
visit(nextPosition);
}
nextPosition = new Position(position.x, position.y - 1, position);
if (isVisitable(nextPosition)) {
queue.offer(nextPosition);
visit(nextPosition);
}
} else {
break;
}
}
Position position = predecessors.getLast();
if (position != null) {
do {
path.push(position);
position = position.predecessor;
} while (position != null);
shortestPath = new Position[path.size()];
int i = 0;
while (!path.isEmpty()) {
shortestPath[i++] = path.pop();
}
}
cleanUp();
return shortestPath;
}
private void next(Position position) {
stepForward(position);
if (shortestPath == null || path.size() < shortestPath.length) {
if (!endFound(position)) {
Position nextPosition = new Position(position.x + 1, position.y);
if (isVisitable(nextPosition)) {
next(nextPosition);
}
nextPosition = new Position(position.x, position.y + 1);
if (isVisitable(nextPosition)) {
next(nextPosition);
}
nextPosition = new Position(position.x - 1, position.y);
if (isVisitable(nextPosition)) {
next(nextPosition);
}
nextPosition = new Position(position.x, position.y - 1);
if (isVisitable(nextPosition)) {
next(nextPosition);
}
} else {
shortestPath = path.toArray(new Position[0]);
}
}
stepBack();
}
private boolean isVisitable(Position position) {
return position.y >= 0
&& position.x >= 0
&& position.y < matrix.length
&& position.x < matrix[position.y].length
&& (matrix[position.y][position.x] == '1' || endFound(position));
}
private boolean endFound(Position position) {
return matrix[position.y][position.x] == 'E';
}
private void stepForward(Position position) {
path.push(position);
if (matrix[position.y][position.x] == '1') {
matrix[position.y][position.x] = 'V';
}
}
private void stepBack() {
Position position = path.pop();
if (matrix[position.y][position.x] == 'V') {
matrix[position.y][position.x] = '1';
}
}
private void visit(Position position) {
if (matrix[position.y][position.x] == '1') {
matrix[position.y][position.x] = 'V';
}
}
private void findStart() {
if (start != null) {
return;
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 'S') {
start = new Position(j, i);
}
}
}
}
private void cleanUp() {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 'V') {
matrix[i][j] = '1';
}
}
}
}
public static void main(String[] args) {
ShortestPath sp = new ShortestPath(new char[][] { { '1', '1', '1', '1', '1' },
{ 'S', '1', 'X', '1', '1' }, { '1', '1', '1', '1', '1' },
{ 'X', '1', '1', 'E', '1' }, { '1', '1', '1', '1', 'X' } });
Position[] path = sp.getPathDFS();
if (path != null) {
System.out.println("DFS: " + Arrays.toString(path));
} else {
System.out.println("No path found!");
}
path = sp.getPathBFS();
if (path != null) {
System.out.println("BFS: " + Arrays.toString(path));
} else {
System.out.println("No path found!");
}
}
}
Finally decided to do both DFS (recursive) and BFS. Wanted to check out the differences between them as to how many steps it takes for each to obtain the solution. If you add some logging to my code you'll find out that for the given example DFS will find the shortest path in 132 steps while BFS will do it in only 22. Enjoy!
Hey! This is a very good code. can you do a Dijkstra's algorithm implementation of this to find the shortest path? Will be very helpful!
Simplest solution
private static int findShortestPathBFS(char arr[][], int startX, int startY)
{
if(arr[startX][startY]=='E') return 0;
int moveX[]=new int[]{0,0,1,-1};
int moveY[]=new int[]{1,-1,0,0};
boolean visited[][]=new boolean[arr.length][arr[0].length];
Queue<QNode> qNodes = new LinkedList<>();
qNodes.add(new QNode(startX,startY,0));
while(!qNodes.isEmpty())
{
QNode currNode=qNodes.remove();
int currX=currNode.x;
int currY=currNode.y;
int currDistance = currNode.distance;
visited[currX][currY]=true;
//System.out.println(arr[currX][currY]);
if(arr[currX][currY]=='E') return currDistance;
for (int i = 0; i < moveX.length; i++)
{
int newX=currX+moveX[i];
int newY=currY+moveY[i];
if(newX>=0&&newX<arr.length&&newY>=0&&newY<arr[0].length&&!visited[newX][newY]&&arr[newX][newY]!='X')
{
qNodes.add(new QNode(newX,newY,currDistance+1));
}
}
}
return -1;
}
private static class QNode
{
int x;
int y;
int distance;
QNode(int x,int y, int distance)
{
this.x=x;
this.y=y;
this.distance=distance;
}
First, find 'S'. Then recursively find every possible solution by making each possible move to squares containing '1'. Mark squares with 'P' as you go, and restore to '1' when returning fro recursion. Keep track of each solution and its length. Find the min length at the end and print out all with that length.
There are 6 solutions with the minimum length of 5.
Running the code:
Dan-Hardy:traverse dhardy$ !./
./traverse.py | more
Starting puzzle:
11111
S1X11
11111
X11E1
1111X
Shortest solution length is 5
Solution:
11111
SPX11
1PPP1
X11E1
1111X
Solution:
11111
SPX11
1PP11
X1PE1
1111X
Solution:
11111
SPX11
1P111
XPPE1
1111X
Solution:
11111
S1X11
PPPP1
X11E1
1111X
Solution:
11111
S1X11
PPP11
X1PE1
1111X
Solution:
11111
S1X11
PP111
XPPE1
1111X
The code:
#!/usr/bin/env python
PUZZLE="""11111
S1X11
11111
X11E1
1111X""".split('\n')
import copy
ROWS = len(PUZZLE)
COLS = len(PUZZLE[0])
def print_puzzle(puzzle):
for line in puzzle:
print ''.join([ch for ch in line])
print ''
def find_path(puzzle, row, col, distance_so_far):
# Find all possible paths to 'E', return solution and length tuples
# test current location, if '1' change to 'P' and continue.
# if 'E' we have a solution
solutions = []
if puzzle[row][col] == 'E':
solution = copy.deepcopy(puzzle)
return [(solution, distance_so_far)]
if puzzle[row][col] not in ('1', 'S'):
return []
left = col == 0
right = col == COLS - 1
top = row == 0
bottom = row == ROWS - 1
orig = puzzle[row][col]
# move in all possible directions and recurse
if not right:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row, col + 1, distance_so_far + 1)
puzzle[row][col] = orig
if not left:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row, col - 1, distance_so_far + 1)
puzzle[row][col] = orig
if not top:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row, col + 1, distance_so_far + 1)
puzzle[row][col] = orig
if not left:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row, col - 1, distance_so_far + 1)
puzzle[row][col] = orig
if not top:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row - 1, col, distance_so_far + 1)
puzzle[row][col] = orig
if not bottom:
if orig != 'S':
puzzle[row][col] = 'P'
solutions += find_path(puzzle, row + 1, col, distance_so_far + 1)
puzzle[row][col] = orig
return solutions
def solve(puzzle):
# find start point S, find shortest path to ending
# point, mark with P for path
for row in range(ROWS):
for col in range(COLS):
if puzzle[row][col] == 'S':
solutions = find_path(puzzle, row, col, 0)
# find solution(s) with shortest path
if not solutions:
print 'No path possible'
return
shortest = min([distance for _, distance in solutions])
print 'Shortest solution length is {}'.format(shortest)
for solution in [solution for solution, distance in solutions if distance == shortest]:
print 'Solution:'
print_puzzle(solution)
if __name__ == '__main__':
# split each line into ch array
puzzle = [[ch for ch in line] for line in PUZZLE]
print 'Starting puzzle:'
print_puzzle(puzzle)
solve(puzzle)
It is similar to finding the shortest path between two given vertices.
Assume the matrix is graph and do BSF kind of traverse.
First take the source
1. visit all the adjacencies which can be traversed and store those into a queue.
2. take elements from queue and do the step 1 till you reach the end point or the queue become empty
In this way you can say whether there is exist a path between two points.
The path you get through this approach is always a shortest path.
But to print the shortest path take a separate array to maintain the parent of each node. The parent if each location (i,j) can be (i-1,j-1) or (i-1,j) etc. based on input.
In order to print the path you have to dfs kind of thing i.e. a recursive approach to remember its parents.
Please let me know If I am wrong.
A DFS will not get you the correct answer unfortunately it MUST be A BFS. A DFS can result in the shortest path, the longest path, anything in between or nothing at all depending on the order of neighbors you take since our graph is pretty loopy.
BFS is pretty much Dijkstra's Shortest Path Algorithm when all weights are 1.
Hi Guys,
I am not a data structure and algorithm guys but more stat guy. But why cant we use the array's location for 2 points and then use Manhattan distance. In this case s is (1,0) and E is (3,3) and then Manhattan distance is 3-1 + 3-0 = 5
typedef struct Position {
Position() : row(-1), col(-1) {}
Position(size_t r, size_t c) : row(r), col(c) {}
size_t row;
size_t col;
} position_t;
bool FindShortestPath(vector<vector<char>>& grid, size_t r, size_t c, queue<string>& result, char dest, char obstacle)
{
string pos, origin;
ostringstream oss, oss1;
set<string> visited;
map<string, string> route;
vector<position_t> positions;
positions.push_back(position_t(r, c));
oss << r << c;
origin = oss.str();
oss.str("");
while (!positions.empty()) {
vector<position_t> nextHops(positions);
positions.clear();
for (vector<position_t>::const_iterator it = nextHops.begin(); it != nextHops.end(); it++) {
oss1.str("");
oss1 << it->row << it->col;
// Go Down
if (it->row + 1 < grid.size())
if (grid[it->row + 1][it->col] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row + 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row + 1][it->col] != obstacle) {// Obstacle. Cancel this route
oss.str("");
oss << it->row + 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row + 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Right
if (it->col + 1 < grid[it->row].size())
if (grid[it->row][it->col + 1] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col + 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col + 1] != obstacle) {
oss.str("");
oss << it->row << it->col + 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col + 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Up
if (it->row > 0)
if (grid[it->row - 1][it->col] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row - 1 << it->col;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row - 1][it->col] != obstacle) {
oss.str("");
oss << it->row - 1 << it->col;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row - 1, it->col));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
// Go Left
if (it->col > 0)
if (grid[it->row][it->col - 1] == dest) {// Reach destination. The first reach is the shortest path
oss.str("");
oss << it->row << it->col - 1;
result.push(oss.str());
pos = oss1.str();
result.push(pos);
while (pos != origin && route.find(pos) != route.end()) {
pos = route[pos];
result.push(pos);
}
return true;
} else if (grid[it->row][it->col - 1] != obstacle) {
oss.str("");
oss << it->row << it->col - 1;
if (visited.find(oss.str()) == visited.end()) { // Prevent loop
positions.push_back(position_t(it->row, it->col - 1));
route.emplace(oss.str(), oss1.str());
visited.emplace(oss.str());
}
}
}
}
return false;
}
This can be solved using BFS.
In this solution, findMinNumStepsBFS takes maze[][], which contains 0s and 1s (1 represents an obstacle), and row and column exit coordinates:
private static int findMinNumStepsBFS(int[][] maze, HashMap<Point, Integer> pathCache, int exitRow, int exitCol) {
LinkedList<PointStepsPair> bfsWorkQueue = new LinkedList<>();
PointStepsPair start = new PointStepsPair(new Point(0, 0), 0);
bfsWorkQueue.add(start);
pathCache.put(start.p, 0);
int leastNumberOfStepsToDestination = Integer.MAX_VALUE;
while (!bfsWorkQueue.isEmpty()) {
PointStepsPair pointStepsPair = bfsWorkQueue.pop();
if (pointStepsPair.p.row == exitRow && pointStepsPair.p.column == exitCol) {
leastNumberOfStepsToDestination = Math.min(pointStepsPair.steps, leastNumberOfStepsToDestination);
} else {
loadAdjacenciesIfNeeded(maze, bfsWorkQueue, pathCache, pointStepsPair);
}
}
if (leastNumberOfStepsToDestination == Integer.MAX_VALUE)
return -1;
return leastNumberOfStepsToDestination;
}
private static void loadAdjacenciesIfNeeded(int[][] maze, LinkedList<PointStepsPair> workingQueue, HashMap<Point, Integer> pathTaken, PointStepsPair pointStepsPair) {
int row = pointStepsPair.p.row;
int col = pointStepsPair.p.column;
int newSteps = pointStepsPair.steps + 1;
Point down = new Point(row + 1, col);
if (canMoveInDirection(maze, down)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, down);
}
Point up = new Point(row - 1, col);
if (canMoveInDirection(maze, up)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, up);
}
Point right = new Point(row, col + 1);
if (canMoveInDirection(maze, right)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, right);
}
Point left = new Point(row, col - 1);
if (canMoveInDirection(maze, left)) {
updateCacheAndWorkingQueueIfNeeded(workingQueue, pathTaken, newSteps, left);
}
}
private static void updateCacheAndWorkingQueueIfNeeded(LinkedList<PointStepsPair> workingQueue, HashMap<Point, Integer> pathTaken, int newSteps, Point down) {
if (pathTaken.containsKey(down)) {
Integer steps = pathTaken.get(down);
if (steps > newSteps) {
workingQueue.add(new PointStepsPair(down, newSteps));
pathTaken.put(down, newSteps);
}
} else {
workingQueue.add(new PointStepsPair(down, newSteps));
pathTaken.put(down, newSteps);
}
}
private static boolean canMoveInDirection(int[][] maze, Point p) {
return p.row < maze.length && p.row >= 0 && p.column < maze[0].length && p.column >= 0 && maze[p.row][p.column] != 1;
}
static class PointStepsPair {
public Point p;
public int steps;
public PointStepsPair(Point p, int steps) {
this.p = p;
this.steps = steps;
}
}
public static class Point {
public int row, column;
public Point(int row, int column) {
this.row = row;
this.column = column;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Point point = (Point) o;
return row == point.row &&
column == point.column;
}
@Override
public int hashCode() {
return Objects.hash(row, column);
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
public class RatMaze
{
private int columns, rows;
private int[,] ratMatrix = null;
private int[,] solutionMatrix = null;
// intializing the solution matrix with 0
private void intializeMatrx(int r, int c)
{
solutionMatrix = new int[r, c];
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
solutionMatrix[i, j] = 0;
}
}
}
// constructor to intialize the required information
public RatMaze(int r, int c, int[,] mat)
{
this.columns = c;
this.rows = r;
this.ratMatrix = mat;
intializeMatrx(r, c);
}
// printing the solution matrix
public void printpath()
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
Console.Write(" " + solutionMatrix[i, j]);
}
Console.WriteLine("");
}
}
// for checking whethere if it is possible to traverset the cell
public Boolean isSafeTraverse(int [,]mat , int x, int y ) {
if(x>=0 && x<= rows-1 && y>=0 && y<= columns-1 && mat[x,y] != 0 )
{
return true;
}
return false;
}
// can traverse right , left , top , up
// 0==> wall , 1==> source , 2==> destinatio , 3== empty cells
public void isTherePathBetweenTwoCellsOfMatrix(int x, int y) {
if (traversingTheMatrix(ratMatrix, x, y, solutionMatrix))
{
Console.WriteLine("Yes !! path exists");
printpath();
}
else
{
Console.WriteLine("No path exists in matrix");
}
}
public Boolean traversingTheMatrix(int [,] problem, int x, int y , int[,] solution)
{
// if already traverse the cell
if (x >= 0 && x <= rows - 1 && y>=0 && y<=columns-1 && solution[x, y] == 1) return false;
if (isSafeTraverse(problem, x, y))
{
solution[x, y] = 1;
if (problem[x, y] == 2) return true;
if (traversingTheMatrix(problem, x + 1, y, solution)) // down
{ return true;
}
if (traversingTheMatrix(problem, x - 1, y, solution)) { return true; } //top
if (traversingTheMatrix(problem, x, y + 1, solution)) { return true; } // right
if (traversingTheMatrix(problem, x, y - 1, solution)) { return true; } // left
solution[x, y] = 0; // backtracking and set it to 0
return false;
}
return false;
}
}
}
// main class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
class MainClass
{
static void Main(string[] args)
{
// 2 question
// can traverse right , left , top , up
// 0==> wall , 1==> source , 2==> destinatio , 3== empty cells
int[,] majeProblemWithSD = new int[4, 5] {
{0, 3, 3, 3, 0},
{0, 3, 0, 3, 3},
{3, 3, 3, 0, 2},
{1, 0, 3, 3, 3}
};
RatMaze solObj = new RatMaze(4, 5, majeProblemWithSD);
solObj.isTherePathBetweenTwoCellsOfMatrix(3, 0);
Console.ReadKey();
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
public class RatMaze
{
private int columns, rows;
private int[,] ratMatrix = null;
private int[,] solutionMatrix = null;
// intializing the solution matrix with 0
private void intializeMatrx(int r, int c)
{
solutionMatrix = new int[r, c];
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
solutionMatrix[i, j] = 0;
}
}
}
// constructor to intialize the required information
public RatMaze(int r, int c, int[,] mat)
{
this.columns = c;
this.rows = r;
this.ratMatrix = mat;
intializeMatrx(r, c);
}
// printing the solution matrix
public void printpath()
{
for (int i = 0; i < rows; i++)
{
for (int j = 0; j < columns; j++)
{
Console.Write(" " + solutionMatrix[i, j]);
}
Console.WriteLine("");
}
}
// for checking whethere if it is possible to traverset the cell
public Boolean isSafeTraverse(int [,]mat , int x, int y ) {
if(x>=0 && x<= rows-1 && y>=0 && y<= columns-1 && mat[x,y] != 0 )
{
return true;
}
return false;
}
// can traverse right , left , top , up
// 0==> wall , 1==> source , 2==> destinatio , 3== empty cells
public void isTherePathBetweenTwoCellsOfMatrix(int x, int y) {
if (traversingTheMatrix(ratMatrix, x, y, solutionMatrix))
{
Console.WriteLine("Yes !! path exists");
printpath();
}
else
{
Console.WriteLine("No path exists in matrix");
}
}
public Boolean traversingTheMatrix(int [,] problem, int x, int y , int[,] solution)
{
// if already traverse the cell
if (x >= 0 && x <= rows - 1 && y>=0 && y<=columns-1 && solution[x, y] == 1) return false;
if (isSafeTraverse(problem, x, y))
{
solution[x, y] = 1;
if (problem[x, y] == 2) return true;
if (traversingTheMatrix(problem, x + 1, y, solution)) // down
{ return true;
}
if (traversingTheMatrix(problem, x - 1, y, solution)) { return true; } //top
if (traversingTheMatrix(problem, x, y + 1, solution)) { return true; } // right
if (traversingTheMatrix(problem, x, y - 1, solution)) { return true; } // left
solution[x, y] = 0; // backtracking and set it to 0
return false;
}
return false;
}
}
}
// main class
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Test
{
class MainClass
{
static void Main(string[] args)
{
// 2 question
// can traverse right , left , top , up
// 0==> wall , 1==> source , 2==> destinatio , 3== empty cells
int[,] majeProblemWithSD = new int[4, 5] {
{0, 3, 3, 3, 0},
{0, 3, 0, 3, 3},
{3, 3, 3, 0, 2},
{1, 0, 3, 3, 3}
};
RatMaze solObj = new RatMaze(4, 5, majeProblemWithSD);
solObj.isTherePathBetweenTwoCellsOfMatrix(3, 0);
Console.ReadKey();
}
}
}
#Solotion in Python with BFS
import Queue
arr = [
[1 , 1 , 1 , 1 , 1 ],
['S', 1 ,'X', 1 , 1 ],
[1 , 1 , 1 , 1 , 1 ],
['X', 1 , 1 ,'E', 1 ],
[1 , 1 , 1 , 1 ,'X']
]
def getKeyByValue(dict,value):
for key , val in dict.iteritems():
if val == value:
return key
def BFS(arr):
d = {}
color = {}
pie = {}
for l in range(0,len(arr)):
for u in range(0,len(arr[l])):
if arr[l][u] == 1:
arr[l][u] = None
if arr[l][u] == 'X':
color[(l,u)] = 'B'
else:
color[(l,u)] = 'W'
d[(l,u)] = arr[l][u]
pie[(l,u)] = None
Q = Queue.Queue(maxsize = 100)
sKey = getKeyByValue(d, 'S')
eKey = getKeyByValue(d, 'E')
d[sKey] = 0
Q.put(sKey)
color[sKey] = 'G'
while not Q.empty():
u = Q.get()
uAdj = []
maxAdj = [ (u[0]-1,u[1]) , (u[0]+1,u[1]) , (u[0],u[1]-1) , (u[0],u[1]+1) ]
for pAdj in maxAdj:
if pAdj in d:
uAdj.append(pAdj)
for v in uAdj:
if color[v] == 'W':
Q.put(v)
color[v] = 'G'
d[v] = d.get(u) + 1
pie[v] = u
if v == eKey:
Q.queue.clear()
break
color[u] = 'B'
shortestPath = [eKey]
runer = eKey
while not pie[runer] == sKey:
runer = pie[runer]
shortestPath.append(runer)
shortestPath.append(sKey)
print(shortestPath)
BFS(arr)
import Queue
{}
arr = [
[1 , 1 , 1 , 1 , 1 ],
['S', 1 ,'X', 1 , 1 ],
[1 , 1 , 1 , 1 , 1 ],
['X', 1 , 1 ,'E', 1 ],
[1 , 1 , 1 , 1 ,'X']
]
def getKeyByValue(dict,value):
for key , val in dict.iteritems():
if val == value:
return key
def BFS(arr):
d = {}
color = {}
pie = {}
for l in range(0,len(arr)):
for u in range(0,len(arr[l])):
if arr[l][u] == 1:
arr[l][u] = None
if arr[l][u] == 'X':
color[(l,u)] = 'B'
else:
color[(l,u)] = 'W'
d[(l,u)] = arr[l][u]
pie[(l,u)] = None
Q = Queue.Queue(maxsize = 100)
sKey = getKeyByValue(d, 'S')
eKey = getKeyByValue(d, 'E')
d[sKey] = 0
Q.put(sKey)
color[sKey] = 'G'
while not Q.empty():
u = Q.get()
uAdj = []
maxAdj = [ (u[0]-1,u[1]) , (u[0]+1,u[1]) , (u[0],u[1]-1) , (u[0],u[1]+1) ]
for pAdj in maxAdj:
if pAdj in d:
uAdj.append(pAdj)
for v in uAdj:
if color[v] == 'W':
Q.put(v)
color[v] = 'G'
d[v] = d.get(u) + 1
pie[v] = u
if v == eKey:
Q.queue.clear()
break
color[u] = 'B'
shortestPath = [eKey]
runer = eKey
while not pie[runer] == sKey:
runer = pie[runer]
shortestPath.append(runer)
shortestPath.append(sKey)
print(shortestPath)
BFS(arr)
public class Amazon_ShortestPathIn2DGrid {
public int shortestPath(char[][] matrix) {
int s_row = 0, s_col = 0;
boolean flag = false;
for (s_row = 0; s_row < matrix.length; s_row++) {
for (s_col = 0; s_col < matrix[0].length; s_col++) {
if (matrix[s_row][s_col] == 'S') flag = true;
if (flag) break;
}
if (flag) break;
}
return shortestPath(matrix, s_row, s_col);
}
public int shortestPath(char[][] matrix, int s_row, int s_col) {
int count = 0;
Queue<int[]> nextToVisit = new LinkedList<>();
nextToVisit.offer(new int[]{s_row, s_col});
Set<int[]> visited = new HashSet<>();
Queue<int[]> temp = new LinkedList<>();
while (!nextToVisit.isEmpty()) {
int[] position = nextToVisit.poll();
int row = position[0];
int col = position[1];
if (matrix[row][col] == 'E')
return count;
if (row > 0 && !visited.contains(new int[]{row-1, col}) && matrix[row-1][col] != 'X')
temp.offer(new int[]{row-1, col});
if (row < matrix.length-1 && !visited.contains(new int[]{row+1, col}) && matrix[row+1][col] != 'X')
temp.offer(new int[]{row+1, col});
if (col > 0 && !visited.contains(new int[]{row, col-1}) && matrix[row][col-1] != 'X')
temp.offer(new int[]{row, col-1});
if (col < matrix[0].length-1 && !visited.contains(new int[]{row, col+1}) && matrix[row][col+1] != 'X')
temp.offer(new int[]{row, col+1});
if (nextToVisit.isEmpty() && !temp.isEmpty()) {
nextToVisit = temp;
temp = new LinkedList<>();
count++;
}
}
return count;
}
public static void main(String[] args) {
char[][] matrix = {{'S','X','1','1','1'},
{'1','X','X','1','1'},
{'1','1','1','1','1'},
{'X','1','1','E','1'},
{'1','1','1','1','X'}};
Amazon_ShortestPathIn2DGrid ama = new Amazon_ShortestPathIn2DGrid();
System.out.println(ama.shortestPath(matrix));
}
}
package gridnavigation;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;
import gridnavigation.GridNavigationTest.Direction;
public class GridNavigationTest {
public static final int[][] navigableGrid = new int[][] {
{ 1, 1, 1, 1 },
{ 1, 0, 0, 1 },
{ 1, 0, 1, 1 },
{ 1, 0, 1, 0 },
{ 1, 1, 9, 0 }
};
public enum Direction {
UP, DOWN, RIGHT, LEFT;
public Direction reverse() {
Direction reverse = null;
if (this.equals(Direction.UP)) {
reverse = DOWN;
} else if (this.equals(Direction.DOWN)) {
reverse = UP;
} else if (this.equals(Direction.RIGHT)) {
reverse = LEFT;
} else if (this.equals(Direction.LEFT)) {
reverse = RIGHT;
}
return reverse;
}
};
private static final Map<String, PathNode> nodesRegistry = new TreeMap<>();
private static final RouteRegistry routeRegistry = new RouteRegistry();
private static final String keyRefDelimiter = ":";
private static final String keyRefFormat = "%d" + keyRefDelimiter + "%d";
private static PathNode destinationNode = null;
public static void main(String... arguments) {
createNodesRegistry();
execTraceRoute();
printSignificantRoute();
}
private static void printSignificantRoute() {
String shortestRoute = Arrays.toString(routeRegistry.getShortestRoute());
System.out.println("-> Shortest\t: " + shortestRoute);
String longestRoute = Arrays.toString(routeRegistry.getLongestRoute());
System.out.println("-> Longest\t: " + longestRoute);
}
private static void createNodesRegistry() {
for (int rowCount = 0; rowCount < navigableGrid.length; rowCount++) {
for (int colCount = 0; colCount < navigableGrid[rowCount].length; colCount++) {
// add current element's node representation to the nodes map, only if it is
// active (value > 0)
if (navigableGrid[rowCount][colCount] > 0) {
IntPair point = new IntPair(rowCount, colCount);
int value = navigableGrid[rowCount][colCount];
PathNode currentElementNode = new PathNode(point, value);
nodesRegistry.put(String.format(keyRefFormat, rowCount, colCount), currentElementNode);
// set adjacent references
setAdjacentReference(currentElementNode, rowCount - 1, colCount, Direction.UP);
setAdjacentReference(currentElementNode, rowCount + 1, colCount, Direction.DOWN);
setAdjacentReference(currentElementNode, rowCount, colCount + 1, Direction.RIGHT);
setAdjacentReference(currentElementNode, rowCount, colCount - 1, Direction.LEFT);
if (currentElementNode.getNodeValue() == 9) {
destinationNode = currentElementNode;
}
}
}
}
}
private static void setAdjacentReference(PathNode currentNode, int row, int col, Direction direction) {
PathNode adjacentNode = nodesRegistry.get(String.format(keyRefFormat, row, col));
if (adjacentNode != null) {
currentNode.setAdjacentNode(direction, adjacentNode);
// set the reverse lookup link
if (adjacentNode.getAdjacentNode(direction.reverse()) == null) {
adjacentNode.setAdjacentNode(direction.reverse(), currentNode);
}
}
}
private static void execTraceRoute() {
// initialize reverse tracing from the destination
destinationNode.traceRoute(routeRegistry, null);
}
}
class PathNode {
private int nodeValue = 0;
private Map<Direction, PathNode> adjacentNodes = new HashMap<>();
private IntPair location = null;
public PathNode() {
super();
}
public PathNode(IntPair location, int value) {
super();
this.location = location;
this.nodeValue = value;
}
public void traceRoute(RouteRegistry routeRegistry, PathNode fromNode) {
if (!this.isStartNode()) {
for (Entry<Direction, PathNode> entry : this.adjacentNodes.entrySet()) {
PathNode node = entry.getValue();
if (!node.equals(fromNode)) {
routeRegistry.put(this.location);
node.traceRoute(routeRegistry, this);
}
}
} else {
routeRegistry.put(this.location);
}
}
public int getNodeValue() {
return this.nodeValue;
}
public void setNodeValue(int value) {
this.nodeValue = value;
}
public void setAdjacentNode(Direction direction, PathNode node) {
this.adjacentNodes.put(direction, node);
}
public PathNode getAdjacentNode(Direction direction) {
return this.adjacentNodes.get(direction);
}
public IntPair getLocation() {
return location;
}
public void setLocation(IntPair location) {
this.location = location;
}
public boolean isStartNode() {
boolean returnValue = false;
if (location != null) {
returnValue = (location.getValue(0) == 0 && location.getValue(1) == 0);
}
return returnValue;
}
public boolean isDestinationNode() {
return (this.getNodeValue() == 9);
}
}
class IntPair {
private Integer[] values = new Integer[2];
public IntPair() {
super();
}
public IntPair(Integer value1, Integer value2) {
super();
this.values[0] = value1;
this.values[1] = value2;
}
public Integer getValue(int index) {
return this.values[index];
}
public void setValue(int index, int value) {
this.values[index] = value;
}
@Override
public String toString() {
return "[" + this.values[0] + ", " + this.values[1] + "]";
}
}
class RouteRegistry {
private int routeIndex = 1;
private Map <String, List<IntPair>> routesMap = new HashMap<>();
public RouteRegistry() {
super();
}
public void put(IntPair point) {
String activeRouteKey = String.format("Route %d", routeIndex);
routesMap.computeIfAbsent(activeRouteKey, k -> new ArrayList<IntPair>());
List<IntPair> routePoints = routesMap.get(activeRouteKey);
routePoints.add(point);
if (point.getValue(0) == 0 && point.getValue(1) == 0) {
routeIndex++;
}
}
public IntPair[] getShortestRoute() {
IntPair[] routeArray = null;
List<IntPair> shortestRoute = null;
for (Entry<String, List<IntPair>> routeEntry : routesMap.entrySet()) {
List<IntPair> route = routeEntry.getValue();
if (shortestRoute == null || shortestRoute.size() > route.size()) {
shortestRoute = route;
}
}
if (shortestRoute != null) {
routeArray = shortestRoute.toArray(new IntPair[shortestRoute.size()]);
} else {
routeArray = new IntPair[0];
}
return routeArray;
}
public IntPair[] getLongestRoute() {
IntPair[] routeArray = null;
List<IntPair> longestRoute = null;
for (Entry<String, List<IntPair>> routeEntry : routesMap.entrySet()) {
List<IntPair> route = routeEntry.getValue();
if (longestRoute == null || longestRoute.size() < route.size()) {
longestRoute = route;
}
}
if (longestRoute != null) {
routeArray = longestRoute.toArray(new IntPair[longestRoute.size()]);
} else {
routeArray = new IntPair[0];
}
return routeArray;
}
}
Takes lot of memory but it works...
- opb2486 August 02, 2014#include <stdio.h> #include <stdlib.h> char arr[5][5]={ {'1','1','1','1','1'}, {'1','S','X','1','1'}, {'1','1','1','1','1'}, {'X','1','1','E','1'}, {'1','1','1','1','X'} }; int minimum[20]; int ind=0; void addToMin(int len) { minimum[ind++]=len; } int IsInPath(int (*path)[5],int r,int c) { if(path[r][c]==0) return 0; else return 1; } int isValid(int r,int c) { if((r>=0 && r<=4) && (c>=0 && c<=4)) return 1; else return 0; } void findMin(int (*path)[5],int len,int r,int c) { int path2[5][5]; int i,j; for(i=0;i<5;i++) for(j=0;j<5;j++) path2[i][j]=0; if(arr[r][c]=='E') { addToMin(len); } else if(arr[r][c]=='X' || (arr[r][c]=='1' && IsInPath(path,r,c))) { return; } else if((arr[r][c]=='1' && !IsInPath(path,r,c)) || arr[r][c]=='S') { for(i=0;i<5;i++) for(j=0;j<5;j++) path2[i][j]=path[i][j]; path2[r][c]=1; len++; if(isValid(r,c-1)) findMin(path2,len,r,c-1); if(isValid(r-1,c)) findMin(path2,len,r-1,c); if(isValid(r,c+1)) findMin(path2,len,r,c+1); if(isValid(r+1,c)) findMin(path2,len,r+1,c); } } int main() { int i,j,flag=0,min=9999; int path[5][5]; for(i=0;i<5;i++) for(j=0;j<5;j++) path[i][j]=0; for(i=0;i<5;i++) { for(j=0;j<5;j++) { if(arr[i][j]=='S') { findMin(path,0,i,j); flag=1; break; } } if(flag==1) break; } for(i=0;i<ind;i++) { if(minimum[i]<min) min=minimum[i]; } printf("Minimum Distance =%d",min); return 0; }