forked from prateekshyap/DSA
-
Notifications
You must be signed in to change notification settings - Fork 0
/
LastDayWhereYouCanStillCross.java
73 lines (67 loc) · 1.88 KB
/
LastDayWhereYouCanStillCross.java
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
/*https://leetcode.com/problems/last-day-where-you-can-still-cross/*/
class Pair
{
int i, j;
Pair(int i, int j)
{
this.i = i;
this.j = j;
}
public String toString()
{
return "("+this.i+","+this.j+")";
}
}
class Solution {
int[][] cells;
int[][] pos = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
int row, col;
public int latestDayToCross(int row, int col, int[][] cells) {
this.cells = cells;
this.row = row;
this.col = col;
int low = 0, high = cells.length-1, mid, result = -1;
while (low <= high)
{
mid = low+(high-low)/2;
if (isFeasible(mid))
{
result = mid;
low = mid+1;
}
else high = mid-1;
}
return result+1;
}
private boolean isFeasible(int day)
{
int[][] mat = new int[row][col];
int len, i, j, r, c;
Pair p;
for (i = 0; i <= day; ++i)
mat[cells[i][0]-1][cells[i][1]-1] = 1;
Queue<Pair> queue = new LinkedList<Pair>();
for (i = 0; i < col; ++i)
if (mat[0][i] == 0)
queue.add(new Pair(0,i));
boolean[][] visited = new boolean[row][col];
while (!queue.isEmpty())
{
len = queue.size();
for (i = 0; i < len; ++i)
{
p = queue.poll();
if (p.i < 0 || p.i >= row || p.j < 0 || p.j >= col || visited[p.i][p.j] || mat[p.i][p.j] == 1) continue;
if (p.i == row-1) return true;
visited[p.i][p.j] = true;
for (j = 0; j < 4; ++j)
{
r = p.i+pos[j][0];
c = p.j+pos[j][1];
queue.add(new Pair(r,c));
}
}
}
return false;
}
}