섬 다리 퍼즐

Alice는 스도쿠 같은 퍼즐을 아주 좋아한다. 최근 그녀는 새로운 퍼즐을 발견했다. 이 퍼즐은 직사각형 격자에서 진행된다. 일부 칸에는 1부터 8까지의 숫자가 적혀 있으며, 이 칸들을 "섬"이라고 부른다. 나머지 칸은 비어 있다. 두 섬이 변을 공유하며 이웃할 수 없다. 목표는 다리를 그어 모든 섬을 연결하는 것이다. 다리는 다음 조건을 지켜야 한다.

• 다리는 서로 다른 두 섬을 잇고, 두 섬 사이를 직선으로 지난다.
• 다리는 가로 또는 세로로만 놓이며, 대각선으로는 놓을 수 없다.
• 다리는 다른 다리나 섬을 가로지를 수 없다.
• 두 섬을 잇는 다리는 최대 두 개다.
• 각 섬에 연결된 다리 수는 그 섬에 적힌 숫자와 같아야 한다.
• 다리로 모든 섬이 하나의 연결된 무리를 이뤄야 한다.

풀이가 하나로 정해지지 않을 수 있다. 아래 그림은 왼쪽이 문제의 예이고 오른쪽이 그 풀이 중 하나다(격자는 그려 두지 않았다).

각 테스트는 하나 이상의 서브테스트로 이루어지며, 각 서브테스트는 이 퍼즐의 한 사례다. 프로그램은 채점기와 함께 컴파일되고, 채점기가 서브테스트를 차례로 입력한다. 채점기는 프로그램이 잘못된 풀이를 출력하거나, 프로그램이 스스로 멈추기로 하거나, 서브테스트가 끝나기 전에 제한 시간이 지나면 멈춘다. 테스트의 점수는 맞힌 서브테스트 수에 비례한다.

2 ≤ numRows, numColumns ≤ 47 2 ≤ numIslands ≤ 200