백준 1080 행렬

https://www.acmicpc.net/problem/1080

이 문제는 행렬을 최소한으로 뒤집어 원하는 행렬의 모양을 만드는 문제이다.

3x3만큼의 크기의 윈도우를 움직인다고 생각해보자.
(0,0)에 있는 배열의 값은 오로지 [0,0] ~ [2,2]에 의해서만 바뀐다.
이를 바탕으로 생각했을때 만약 (0,0)의 값이 다르다면, 무조건 해당 위치는 토글을 하여야 한다.

이를 바탕으로 생각하면 (0,1)은 [0,0] ~ [2,2]의 윈도우와 [0,1] ~ [2,3]의 윈도우에만 영향을 받는다.

결론적으로 윈도우를 하나씩 밀어가며 제일 왼쪽 상단에 있는 값을 바꾸어야 하는지를 바탕으로 토글을 해나가면 된다.

n,m = list(map(int,input().split()))
before = []
after = []
ans = 0
for i in range(n):
    before.append(list(map(int,input())))
for i in range(n):
    after.append(list(map(int,input())))

def toggle(x,y):
    for i in range(x,x+3):
        for j in range(y,y+3):
            if before[i][j] == 0:
                before[i][j] = 1
            else:
                before[i][j] = 0

for i in range(n-2):
    for j in range(m-2):
        if before[i][j] != after[i][j]:
            toggle(i,j)
            ans += 1

for i in range(n):
    for j in range(m):
        if before[i][j] != after[i][j]:
            ans = -1
print(ans)