Python에서 안전 거리를 유지할 수 있는 k의 최대값을 찾는 프로그램

이진 행렬이 있다고 가정합니다. 여기서 0은 빈 셀을 의미하고 1은 사람이 있는 셀을 의미합니다. 두 셀 사이의 거리는 x 좌표의 차이와 y 좌표의 차이 사이의 최대값입니다. 이제 행렬의 셀에서 각 사람까지의 거리와 행렬의 각 변이 모두 k보다 크거나 같은 빈 정사각형이 있는 경우 행렬은 인수 k로 안전한 것으로 간주됩니다. 안전할 수 있는 요인 k의 최대값을 찾아야 합니다.

따라서 입력이 다음과 같으면

중간 셀에서 그리드의 각 사람까지의 거리는 최소 1이므로 출력은 1이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• N :=A의 크기

• M :=A[0]의 크기

• 범위 0에서 N까지의 i에 대해 수행

  • 0에서 M 범위의 j에 대해 수행

    • A[i, j] :=A[i, j] XOR 1

• 답변 :=0

• 범위 0에서 N까지의 i에 대해 수행

  • 0에서 M 범위의 j에 대해 수행

    • i와 j가 0이 아니고 A[i, j]가 1이면

      • A[i, j] :=1 + A[i - 1, j], A[i, j - 1] 및 A[i - 1, j - 1]의 최소값

      • as =A[i, j] 및 ans

        의 최대값

• 반환(ans + 1) / 2

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution:def solve(self, A):N =len(A) M =len(A[0]) for i in range(N):for j in range(M):A[i][ j] ^=1 ans =0 for i in range(N):for j in range(M):if i and j and A[i][j]:A[i][j] =1 + min(A [i - 1][j], A[i][j - 1], A[i - 1][j - 1]) ans =max(A[i][j], ans) return (ans + 1 ) // 2ob =솔루션() 행렬 =[ [0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 1, 0, 1, 0], [0, 1, 1, 1, 0], [0, 0, 0, 0, 0],]print(ob.solve(매트릭스))

입력

출력

1