동전 뒤집기

• 열과 행이 모두 홀수개인 경우만 주어진다는 점을 우선 기억해두자.
• 한 열을 플립할때 1의 갯수의 홀짝이 바뀌는 열과 행을 생각해보면, 열은 플립한 열만 바뀌고, 행은 모든 행이 바뀐다. 열과 행을 합쳐서 짝수개가 바뀌게 된다. 한 행을 플립할 때에도 마찬가지. 결국 모든 행동은 1이 홀수개인 열과 행의 갯수를 변화시키게 될텐데, 그 변화량은 항상 짝수개라는 것을 알수 있다. 따라서 처음에 1의 갯수가 홀수인 행과 열을 합친 갯수가 홀수개라면, 목표를 달성하는 방법이 불가능하다.
• 이제 뒤집어야 하는 최소 횟수는 얼마일까. 당연히 똑같은 행/열을 두번 이상 뒤집는것은 의미가 없으니까 횟수는 최대 N+M번이다. 여차하면 BFS등으로 풀어도 되긴 하다.
• 하지만 간단하게 생각하면 쉽게 답을 구할수 있다.. 1의 갯수가 홀수인 행과 짝수인 행이 섞여있는 경우, 열만 뒤집어서는 아무리 뒤집어도 여전히 홀수인 행과 짝수인 행이 남는다. 먼저 홀수인 행을 모두 뒤집어서 모든 행을 짝수로 만들거나, 짝수인 행을 모두 뒤집어서 모든 행을 홀수로 만든 다음에, 열을 뒤집으면 된다. 열을 뒤집는 것은 홀수인 열을 모두 뒤집으면 끝난다. 결국 처음에 홀수인 행을 뒤집거나, 짝수인 행을 뒤집거나 두가지 선택지가 있고, 각각에 대해서 뒤집는 총 횟수를 계산해서 작은 쪽을 택하면 된다. 이해가 잘 안되면 코드를 참조.
• 시간복잡도는 O(n+m)

"""Solution code for "BOJ 1640. 동전 뒤집기".

- Problem link: https://www.acmicpc.net/problem/1640
- Solution link: http://www.teferi.net/ps/problems/boj/1640

Tags: [ad hoc]
"""

import sys


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    grid = [sys.stdin.readline().rstrip() for _ in range(N)]

    odd_row_count = sum(row.count('1') % 2 for row in grid)
    odd_col_count = sum(col.count('1') % 2 for col in zip(*grid))

    if (odd_row_count + odd_col_count) % 2 == 1:
        print('-1')
        return

    if odd_row_count % 2 == 0:
        answer = odd_row_count + odd_col_count
    else:
        answer = odd_row_count + M - odd_col_count
    answer = min(answer, M + N - answer)

    print(answer)


if __name__ == '__main__':
    main()