-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patht764LargestPlusSign.java
More file actions
59 lines (54 loc) · 1.51 KB
/
t764LargestPlusSign.java
File metadata and controls
59 lines (54 loc) · 1.51 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
import java.util.HashSet;
import java.util.Set;
public class t764LargestPlusSign {
public int orderOfLargestPlusSign(int N, int[][] mines) {
int[][] dp = new int[505][505];
Set<Integer> s = new HashSet<Integer>();
for(int i=0;i<mines.length;i++){
s.add(mines[i][0]*N+mines[i][1]);
}
int res = 0;
for(int i=0;i<N;i++){
int cut = 0;
for(int j=0;j<N;j++){
if(!s.contains(i*N+j)){
cut++;
dp[i][j] = cut;
}else{
cut=0;
}
}
cut = 0;
for(int j=N-1;j>=0;j--){
if(!s.contains(i*N+j)){
cut++;
dp[i][j] = Math.min(dp[i][j],cut);
}else{
cut=0;
}
}
}
for(int j=0;j<N;j++){
int cut = 0;
for(int i=0;i<N;i++){
if(!s.contains(i*N+j)){
cut++;
dp[i][j] = Math.min(dp[i][j],cut);
}else{
cut=0;
}
}
cut = 0;
for(int i=N-1;i>=0;i--){
if(!s.contains(i*N+j)){
cut++;
dp[i][j] = Math.min(dp[i][j],cut);
res = Math.max(dp[i][j],res);
}else{
cut=0;
}
}
}
return res;
}
}