동전 뒤집기
시간 제한2초메모리 제한128 MB
홀수 크기의 N×M 0/1 격자에서 행이나 열을 뒤집어 모든 행과 열의 1의 개수를 짝수로 만드는 최소 연산 횟수를 구하고, 불가능하면 -1을 출력하는 문제입니다.
문제
N×M 격자에 동전이 놓여 있다. N과 M은 모두 홀수이다. 동전의 앞면은 0, 뒷면은 1로 나타낸다.
한 번의 작업에서는 하나의 행 또는 하나의 열을 선택하고, 그 안에 있는 모든 동전을 뒤집는다. 뒤집힌 동전은 0이 1로, 1이 0으로 바뀐다.
모든 행과 모든 열에서 1의 개수가 짝수가 되도록 만들고자 한다. 필요한 작업 횟수의 최솟값을 구하라.
입력
첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 1,000 이하인 홀수이다.
다음 N개의 줄에는 각 줄마다 길이가 M인 문자열이 주어진다. 각 문자는 0 또는 1이며, 현재 동전의 상태를 나타낸다.
출력
모든 행과 모든 열에서 1의 개수가 짝수가 되도록 만들기 위해 필요한 작업 횟수의 최솟값을 출력한다. 불가능하다면 -1을 출력한다.
힌트
첫 번째 공개 테스트에서는 가운데 행과 가운데 열을 뒤집으면 조건을 만족한다.