動機
top-down只過了第一次,之後就過不了了
Problem
You are given an integer n
. You have an n x n
binary grid grid
with all values initially 1
's except for some indices given in the array mines
. The ith
element of the array mines
is defined as mines[i] = [xi, yi]
where grid[xi][yi] == 0
.
Return the order of the largest axis-aligned plus sign of 1's contained in grid
. If there is none, return 0
.
An axis-aligned plus sign of 1
's of order k
has some center grid[r][c] == 1
along with four arms of length k - 1
going up, down, left, and right, and made of 1
's. Note that there could be 0
's or 1
's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1
's.
Example 1:
Input: n = 5, mines = [[4,2]]Output: 2Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.
Example 2:
Input: n = 1, mines = [[0,0]]Output: 0Explanation: There is no plus sign, so return 0.
Constraints:
1 <= n <= 500
1 <= mines.length <= 5000
0 <= xi, yi < n
- All the pairs
(xi, yi)
are unique.
Sol
所以就bottom-up
class Solution:
def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
mines = set((x,y) for x,y in mines)
left, right, up, down = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)
for i in range(n):
for j in range(n):
if (i,j) not in mines:
left[(i,j)] += 1+left[(i,j-1)]
up[(i,j)] += 1+up[(i-1,j)]
for i in reversed(range(n)):
for j in reversed(range(n)):
if (i,j) not in mines:
right[(i,j)] += 1+right[(i,j+1)]
down[(i,j)] += 1+down[(i+1,j)]
ret = 0
for i in range(n):
for j in range(n):
ret = max(ret, min(left[(i,j)], up[(i,j)], right[(i,j)], down[(i,j)]))
return ret