[백준] 1080 : 행렬

www.acmicpc.net/problem/1080

1080번: 행렬

---

• 특정 위치에서 뒤집을 경우, 3x3 만큼의 크기를 반드시 뒤집는다.
• 따라서 N-2, N-1 인덱스 같은 위치에서는 뒤집기 연산을 수행할 수 없다.
• 뒤집기 연산의 특성상, [0][0] 을 제외하고 나머지 위치에서는 [0][0] 을 절대 업데이트 할 수 없다.
• 마찬가지로 왼쪽 위부터 오른쪽 아래까지 순서대로 한번씩 뒤집어나간다고 할 때, 이미 지나간 위치에 대해서는 다른 위치에서 뒤집기 연산을 한다고 해도 바뀔 수가 없다.
• 따라서 A와 B를 [0][0], [0][1], [0][2] ... 순서대로 해당 위치의 값을 하나씩 확정시켜나가며 뒤집어준다.

---

N, M = map(int, input().split())

A = [list(map(int, input())) for i in range(N)]
B = [list(map(int, input())) for i in range(N)]

def check():                            # A 와 B 두 행렬이 같은지 검사하는 함수
    for i in range(N):
        for j in range(M):
            if A[i][j] != B[i][j]:
                return False
    return True

def push(r, c):                         # 특정 위치에서 3x3 을 뒤집어주는 함수
    for i in range(3):
        for j in range(3):
            A[r+i][c+j] = int(not A[r+i][c+j])

if N < 3 or M < 3:                      # 애초에 뒤집을 수 없는 행렬이라면 검사하고 종료
    print(0 if check() else -1)
else:
    cnt = 0
    for i in range(N-2):                # [0][0] 부터 [N-3][M-3] 행렬을 검사 
        for j in range(M-2):
            if A[i][j] != B[i][j]:      # 만약 값이 다르다면
                push(i, j)              # 헤딩 위치에서 뒤집어주고
                cnt += 1                # 처리
                if check():
                    print(cnt)
    if not check():                     # 전체 검사 후에도 행렬이 다르다면 -1 출력
        print(-1)