N x N 격자의 셀이 있다고 가정하고 각 셀(x, y)에는 램프가 있습니다. 처음에는 일부 램프가 켜져 있습니다. 램프[i]는 켜져 있는 i번째 램프의 위치입니다. 켜져 있는 각 램프는 x축, y축 및 두 대각선의 모든 사각형에 빛을 발합니다. 이제 i 번째 쿼리, 즉 쿼리[i] =(x, y)의 경우 쿼리에 대한 대답은 셀(x, y)에 불이 들어오면 1이고 그렇지 않으면 0입니다. 각 쿼리(x, y) 후에 우리는 셀(x, y)에 있거나 8방향으로 인접한 모든 램프를 끕니다. 답변 배열을 반환합니다. 각 값 답변[i]은 i번째 쿼리 쿼리[i]의 답변과 같아야 합니다.
따라서 입력이 N =5이고 램프가 [[0,0],[4,4]]이고 쿼리 =[[1,1],[1,0]]이면 출력은 [1 ,0]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
램프 :=주어진 어레이 램프의 쌍 세트
-
지도 생성 x, y, diag1, diag2
-
램프의 각 쌍(i, j)에 대해
-
x[i] :=x[i] + 1, y[j] :=y[j] + 1
-
diag1[i + j] :=diag1[i + j] + 1, diag2[i - j] =diag2[i - j] + 1
-
-
as :=[]
-
C의 각 값 i에 대해
-
a :=i[0], b :=i[1]
-
(x[a] + y[b] + diag1[a + b] + diag2[a - b]> 0인 경우 1인 경우 ans
에 삽입 -
a - 1 ~ + 1 범위의 행
-
b - 1 ~ b + 1 범위의 col에 대해
-
행, 열 쌍이 램프에 있는 경우 -
-
x[행] :=x[행] - 1
-
y[col] :=y[col] - 1
-
diag1[행 + 열] =diag1[행 + 열] - 1
-
diag2[행 - 열] =diag2[행 - 열] - 1
-
램프에서 제거(행, 열)
-
-
-
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
from collections import defaultdict
class Solution(object):
def gridIllumination(self, N, b, C):
lamps = {(i[0], i[1]) for i in b}
x, y, diag1, diag2 = defaultdict(int), defaultdict(int),
defaultdict(int), defaultdict(int)
for i, j in lamps:
x[i] += 1
y[j] += 1
diag1[i + j] += 1
diag2[i - j] += 1
ans = []
for i in C:
a = i[0]
b = i[1]
ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0)
for row in range( a - 1, a + 2):
for col in range(b - 1, b + 2):
if (row, col) in lamps:
x[row] -= 1
y[col] -= 1
diag1[row + col] -= 1
diag2[row - col] -= 1
lamps.remove((row, col))
return ans
ob = Solution()
N = 5
lamps = [[0,0],[4,4]]
query = [[1,1],[1,0]]
print(ob.gridIllumination(N, lamps, query)) 입력
5, [[0,0],[4,4]], [[1,1],[1,0]]
출력
[1, 0]