(짝수) x (짝수) 형태는 모든 경우를 확인할 필요 없이 다항시간 내에 풀리네요.

그리고 그 해는 (같은 칸을 여러번 누르는 것을 제외하고) 유일하기 때문에 한가지 방법 구하면 그게 최소횟수일거고요.


일단 누르는 순서가 상관 없다는점

두 번 누르면 원래대로 돌아간다는 점 때문에

우리는 어디를 눌러야할지 전체 격자판의 subset 중에서 해가 되는 얘를 찾으면 됨.


그런데


XXXX

X___

X___

X___


이런식으로 X가 되어있는 부분을 누르면, 딱 한 칸을 반전시킬 수 있음.

다른 칸도 비슷한 방법으로 하면 되고, 이러면 눌러서 어떤 경우도 만들 수 있는데


누르는 방법의 수와 격자판의 state 수가 같기 때문에 서로 일대일 대응 관계가 있음.

이러면 굳이 최소 횟수를 따질 필요가 없지요.