2차원 행렬 M이 있다고 가정합니다. 이제 각 셀에 색상을 나타내는 값이 포함되고 동일한 색상을 가진 인접 셀(위, 아래, 왼쪽, 오른쪽)이 함께 그룹화됩니다. 이제 한 그룹의 모든 셀을 특정 색상으로 설정하는 작업을 고려하십시오. 그런 다음 마지막으로 모든 셀이 동일한 색상을 갖도록 필요한 최소 작업 수를 찾습니다. 그리고 색상이 변경되면 다시 설정할 수 없습니다.
따라서 입력이 다음과 같으면
| 2 | 2 | 2 | 2 |
| 1 | 1 | 1 | 1 |
| 2 | 3 | 2 | 1 |
그러면 출력은 2가 됩니다. 2가 있는 그룹을 1에 색상으로 채운 다음 3을 1로 채울 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따르겠습니다-
-
행렬이 비어 있으면
-
0 반환
-
-
dfs() 함수를 정의합니다. 이것은 i, j, 행렬, val이 필요합니다.
-
n :=행렬의 행 개수, m :=행렬의 열 개수
-
i <0 또는 i> n - 1 또는 j <0 또는 j> m - 1이면
-
반환
-
-
행렬[i, j]가 -1과 같으면
-
반환
-
-
행렬[i, j]가 val과 같으면
-
행렬[i, j] :=-1
-
dfs(i, j + 1, 행렬, 발)
-
dfs(i + 1, j, 행렬, 발)
-
dfs(i, j - 1, 행렬, 발)
-
dfs(i - 1, j, 행렬, 값)
-
-
그렇지 않으면
-
반환
-
-
기본 방법에서 다음을 수행하십시오-
-
n :=행렬의 행 개수, m :=행렬의 열 개수
-
d :=빈 맵
-
0에서 n-1 사이의 i에 대해 수행
-
0 ~ m-1 범위의 j에 대해 수행
-
발 :=행렬[i,j]
-
val이 -1과 같지 않으면
-
d[발] :=d[발] + 1
-
dfs(i, j, 행렬, 발)
-
-
값에 따라 f의 사전 요소 정렬
-
safe :=l의 마지막 요소
-
해상도 :=0
-
d의 각 키 값 쌍 k 및 v에 대해 수행
-
k가 안전하지 않은 경우
-
res :=res + v
-
-
반환 해상도
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from collections import defaultdict class Solution: def solve(self, matrix): if not matrix: return 0 def dfs(i, j, matrix, val): n, m = len(matrix), len(matrix[0]) if i < 0 or i > n - 1 or j < 0 or j > m - 1: return if matrix[i][j] == -1: return if matrix[i][j] == val: matrix[i][j] = -1 dfs(i, j + 1, matrix, val) dfs(i + 1, j, matrix, val) dfs(i, j - 1, matrix, val) dfs(i - 1, j, matrix, val) else: return n, m = len(matrix), len(matrix[0]) d = defaultdict(int) for i in range(n): for j in range(m): val = matrix[i][j] if val != -1: d[val] += 1 dfs(i, j, matrix, val) l = sorted(d,key=lambda x: d[x]) safe = l[-1] res = 0 for k, v in d.items(): if k != safe: res += v return res ob = Solution() matrix = [ [2, 2, 2, 2], [1, 1, 1, 1], [2, 3, 2, 1] ] print(ob.solve(matrix))
입력
matrix = [[2, 2, 2, 2],[1, 1, 1, 1],[2, 3, 2, 1]]
출력
2