https://www.acmicpc.net/problem/1080
시간 2초, 메모리 128MB
input :
- N M (1 <= N, M <= 50)
- 행렬 A, 그 다음줄부터 행렬 B
output :
- 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력
조건 :
- 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성
어떤 문장을 동일하게 만드시오.
라는 문제에서는 실제로 만들어 버리는 것이 가장 쉬운 방식이다. 조건을 따져서 하려고 한다면 상, 하, 좌, 우 뭐 몇 번을 뒤집어서 만들 수 있는 지 등의 계산이 필요할 것이다.
그런데 행렬 자체가 50 50 이 최대고 거기에 변화를 주는 것의 크기는 또 3 3이니까 10만번도 하지 않는다.
그러니까 a와 b의 값이 다르다면 그냥 변화를 하도록 하고 마지막에는 두 행렬을 비교한다.
import sys
def change(x, y):
for i in range(x, x + 3):
for j in range(y, y + 3):
if a[i][j] == '1':
a[i][j] = '0'
else:
a[i][j] = '1'
n, m = map(int, sys.stdin.readline().split())
a, b, cnt = [list(sys.stdin.readline().rstrip()) for _ in range(n)], [list(sys.stdin.readline().rstrip()) for _ in range(n)], 0
for i in range(n - 2):
for j in range(m - 2):
if a[i][j] != b[i][j]:
change(i, j)
cnt += 1
print(cnt if a == b else -1)
