cho.sh음과 양의 길 (작은 입력)
N행 M열 격자의 모든 칸을 흑백으로 칠할 때 검은 칸과 흰 칸이 각각 양쪽 끝이 하나씩 있는 경로가 되는 경우의 수를 구합니다.
어려움9조합론백트래킹그래프아직 제출이 없습니다시간 제한30초메모리 제한512 MB문제 설명
예제2
문제
행 열 격자가 있다. 각 칸은 검은색(음) 또는 흰색(양)으로 칠해져 있다. 두 칸이 길이 인 변을 공유하면 서로 이웃이다. 검은 칸 전체가 하나의 경로를 이루고 흰 칸 전체도 하나의 경로를 이룰 때, 이 격자를 유효한 격자라고 한다.
칸의 집합 가 경로라는 것은 아래 세 조건을 모두 만족한다는 뜻이다.
- 는 연결되어 있다. 의 어떤 칸에서 출발하든 에 속한 이웃 칸만 밟아 의 나머지 칸에 모두 도달한다.
- 안에서 이웃이 정확히 하나인 칸이 정확히 두 개다. 이 두 칸이 경로의 양 끝이다.
- 나머지 칸은 모두 안에서 이웃이 정확히 둘이다.
아래 그림에서 첫 번째 격자는 유효하다. 두 번째 격자는 검은 칸이 경로를 이루지만 흰 칸이 경로를 이루지 않아 유효하지 않다.
과 이 주어지면 유효한 격자가 몇 개인지 세어라. 대칭은 따지지 않는다. 한 칸이라도 색이 다르면 회전하거나 뒤집어서 서로 겹쳐지더라도 다른 격자로 센다.
입력
첫 줄에 테스트 케이스의 개수 가 주어진다. 다음 개의 줄에는 각각 두 정수 과 이 공백으로 구분되어 주어진다.
출력
각 테스트 케이스마다 Case #x: A 형식으로 한 줄씩 출력한다. 는 1부터 시작하는 테스트 케이스 번호이고, 는 행 열인 유효한 격자의 개수다.