In a 2D grid from (0, 0) to (N-1, N-1), every cell contains a 1, except those cells in the given list mines which are 0. What is the largest axis-aligned plus sign of 1s contained in the grid? Return the order of the plus sign. If there is none, return 0.
Examples of Axis-Aligned Plus Signs of Order k:
Order 1: 000 010 000 Order 2: 00000 00100 01110 00100 00000 Order 3: 0000000 0001000 0001000 0111110 0001000 0001000 0000000
一行(列)经过两次扫描来标记出该行(列)所有位置的Order，总共经过四轮扫描之后获取所有位置的Order从而求出Order最大值
class Solution: def orderOfLargestPlusSign(self, N, mines): """ :type N: int :type mines: List[List[int]] :rtype: int """ banned = {tuple(mine) for mine in mines} depth = [[0] * N for _ in range(N)] answer = 0 for row in range(N): count = 0 for col in range(N): count = 0 if (row, col) in banned else count + 1 depth[row][col] = count count = 0 for col in range(N - 1, -1, -1): count = 0 if (row, col) in banned else count + 1 if count < depth[row][col]: depth[row][col] = count for col in range(N): count = 0 for row in range(N): count = 0 if (row, col) in banned else count + 1 if count < depth[row][col]: depth[row][col] = count count = 0 for row in range(N - 1, -1, -1): count = 0 if (row, col) in banned else count + 1 if count < depth[row][col]: depth[row][col] = count if depth[row][col] > answer: answer = depth[row][col] return answer
0条评论