-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathShortestPath.java
More file actions
115 lines (110 loc) · 4.62 KB
/
ShortestPath.java
File metadata and controls
115 lines (110 loc) · 4.62 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
package assessmentDay;
//
// Implement a function that receives a grid representing a labyrinth and computes the shortest path from the top left corner cell (start) to the bottom right coiner cell (end).
//
// The primary input is a uniform 2D grid representing a labyrinth. Each entry in the grid will be either a 0 or 1. 1 represents a blocked wall, and 0 represents free space.
//
// Your function will receive the dimensions of the grid, and the grid parsed from the input into native language data structures. It should return the length of the shortest path from start (top left cell) to the end (bottom right cell) as a single integer.
//
// You can expect that there is always a path through the labyrinth
//
// Sample input E
//
// 34
//
// Sample output
// 5
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
static int shortestPath(int rows, int cols, int[][] grid) {
boolean[][] visited = new boolean[rows][cols];
int[][] distance = new int[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{0, 0});
visited[0][0] = true;
distance[0][0] = 0;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];
// if we have reached the end
if (row == rows - 1 && col == cols - 1) {
return distance[row][col];
}
// try to move up
if (row > 0 && grid[row - 1][col] == 0 && !visited[row - 1][col]) {
queue.add(new int[]{row - 1, col});
visited[row - 1][col] = true;
distance[row - 1][col] = distance[row][col] + 1;
}
// try to move down
if (row < rows - 1 && grid[row + 1][col] == 0 && !visited[row + 1][col]) {
queue.add(new int[]{row + 1, col});
visited[row + 1][col] = true;
distance[row + 1][col] = distance[row][col] + 1;
}
// try to move left
if (col > 0 && grid[row][col - 1] == 0 && !visited[row][col - 1]) {
queue.add(new int[]{row, col - 1});
visited[row][col - 1] = true;
distance[row][col - 1] = distance[row][col] + 1;
}
// try to move right
if (col < cols - 1 && grid[row][col + 1] == 0 && !visited[row][col + 1]) {
queue.add(new int[]{row, col + 1});
visited[row][col + 1] = true;
distance[row][col + 1] = distance[row][col] + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 1, 0},
{1, 0, 0, 0},
{0, 0, 1, 0}
};
System.out.println(shortestPath(3, 4, grid));
}
}
// boolean[][] visited = new boolean[rows][cols];
// int[][] distance = new int[rows][cols];
// Queue<int[]> queue = new LinkedList<>();
// queue.add(new int[]{0, 0});
// visited[0][0] = true;
// distance[0][0] = 0;
// while (!queue.isEmpty()) {
// int[] current = queue.poll();
// int row = current[0];
// int col = current[1];
// // if we have reached the end
// if (row == rows - 1 && col == cols - 1) {
// return distance[row][col];
// }
// // try to move up
// if (row > 0 && grid[row - 1][col] == 0 && !visited[row - 1][col]) {
// queue.add(new int[]{row - 1, col});
// visited[row - 1][col] = true;
// distance[row - 1][col] = distance[row][col] + 1;
// }
// // try to move down
// if (row < rows - 1 && grid[row + 1][col] == 0 && !visited[row + 1][col]) {
// queue.add(new int[]{row + 1, col});
// visited[row + 1][col] = true;
// distance[row + 1][col] = distance[row][col] + 1;
// }
// // try to move left
// if (col > 0 && grid[row][col - 1] == 0 && !visited[row][col - 1]) {
// queue.add(new int[]{row, col - 1});
// visited[row][col - 1] = true;
// distance[row][col - 1] = distance[row][col] + 1;
// }
// // try to move right
// if (col < cols - 1 && grid[row][col + 1] == 0 && !visited[row][col + 1]) {
// queue.add(new int[]{row, col + 1});
// visited[row][col + 1] = true;
// distance[row][col + 1] = distance[row][col] + 1;
// }
// }
// return -1;