forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 1
/
largest-plus-sign.py
35 lines (32 loc) · 1 KB
/
largest-plus-sign.py
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
# Time: O(n^2)
# Space: O(n^2)
class Solution(object):
def orderOfLargestPlusSign(self, N, mines):
"""
:type N: int
:type mines: List[List[int]]
:rtype: int
"""
lookup = {tuple(mine) for mine in mines}
dp = [[0] * N for _ in xrange(N)]
result = 0
for i in xrange(N):
l = 0
for j in xrange(N):
l = 0 if (i, j) in lookup else l+1
dp[i][j] = l
l = 0
for j in reversed(xrange(N)):
l = 0 if (i, j) in lookup else l+1
dp[i][j] = min(dp[i][j], l)
for j in xrange(N):
l = 0
for i in xrange(N):
l = 0 if (i, j) in lookup else l+1
dp[i][j] = min(dp[i][j], l)
l = 0
for i in reversed(xrange(N)):
l = 0 if (i, j) in lookup else l+1
dp[i][j] = min(dp[i][j], l)
result = max(result, dp[i][j])
return result