7161 : 격자 탈색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N×N 크기의 격자판이 주어지며, 각 칸은 k가지 색(1~k) 중 하나로 칠해져 있습니다. 인접한 격자 칸이 서로 다른 색이 되도록 최소의 칸을 탈색/재색칠하려고 할 때, 이것이 가능한지 여부와 최소 변경 횟수를 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 격자의 크기 N과 색의 수 k가 주어집니다. (1 ≤ N ≤ 4, 1 ≤ k ≤ 4)
둘째 줄부터 N개의 줄에 격자의 현재 색상 정보(N×N)가 공백으로 구분되어 주어집니다.
둘째 줄부터 N개의 줄에 격자의 현재 색상 정보(N×N)가 공백으로 구분되어 주어집니다.
출력 설명
인접 격자가 다른 색을 가지는 유효한 색칠이 가능하면 "YES [최소 변경 횟수]"를 출력하고, 불가능하면 "NO"를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2 2
1 1
1 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
YES 2도움
대각선 방향은 유지하고 2개의 칸을 다른 색(2)으로 변경하면 YES가 됩니다.