라이트 업

Light Up은 펜슬 퍼즐이다. 이 문제에서는 Light Up을 직접 푸는 것이 아니라, 플레이어의 풀이가 올바른지 판정하면 된다.

게임은 정사각형 격자에서 진행된다. 일부 칸은 막혀 있고, 막힌 칸 중 일부에는 0부터 4까지의 숫자가 적혀 있다. 플레이어는 열린 칸에 전구를 놓는다. 각 전구는 위, 아래, 왼쪽, 오른쪽 방향(대각선 제외)으로 격자의 끝이나 막힌 칸에 닿을 때까지 모든 열린 칸을 비춘다. 플레이어는 다음 조건을 만족하도록 전구를 놓아야 한다.

• 열린 칸이 모두 빛을 받는다.
• 두 전구가 서로를 비추지 않는다.
• 숫자가 적힌 막힌 칸은 상하좌우로 바로 인접한 전구의 개수가 그 숫자와 정확히 같아야 한다. 대각선은 세지 않는다.

다음은 예시 격자와 그 풀이이다.

전구가 놓인 격자가 주어졌을 때, 이것이 풀이인지 판정하라. 열린 칸이 하나도 없고 다른 조건을 위반하지 않는다면 자명하게 풀린 것이다.

입력의 첫 줄에 격자의 행과 열의 개수를 나타내는 정수 $n$ ($1≤n≤30$)이 주어진다.

이어지는 $n$개의 줄에는 각각 {., X, ?, 0, 1, 2, 3, 4} 중에서 정확히 $n$개의 문자가 주어진다. .은 열린 칸, X는 막힌 칸, ?는 전구, 숫자 0부터 4는 인접한 전구 개수에 제약이 있는 막힌 칸이다.

입력이 올바른 풀이이면 $1$, 그렇지 않으면 $0$을 한 개의 정수로 출력한다.