파급효과

주어진 숫자 격자가 파급효과 퍼즐의 규칙을 만족하는지 판별한다.

파급효과 퍼즐은 여러 개의 폴리오미노로 나누어진 직사각형 격자에서 진행된다. 폴리오미노는 같은 크기의 정사각형 한 개 이상을 변끼리 이어 붙여 만든 도형이다.

격자의 모든 칸에는 자연수가 하나씩 적혀 있다. 이 배치가 올바르려면 다음 규칙을 모두 만족해야 한다.

• 크기가 k인 폴리오미노에는 1부터 k까지의 자연수가 각각 정확히 한 번씩 나타나야 한다.
• 같은 행이나 같은 열에 같은 숫자 x가 두 번 이상 나타나면, 임의의 두 x 사이에는 적어도 x개의 다른 칸이 있어야 한다. 즉 두 칸의 행 또는 열 위치 차이는 x + 1 이상이어야 한다.

이 문제에서 폴리오미노의 크기는 최대 8이다.

첫째 줄에 테스트 케이스의 수 T가 주어진다. (T <= 100)

각 테스트 케이스의 첫째 줄에는 두 정수 R, C가 주어진다. (4 <= R, C <= 15)

다음 R개 줄에는 격자에 적힌 숫자를 나타내는 길이 C의 문자열이 주어진다. 각 문자는 d_i이며 1 <= d_i <= 8이다.

그다음 R개 줄에는 각 칸이 이웃한 칸과 어떻게 연결되는지를 나타내는 C개의 정수가 주어진다. 이 R x C 표를 descr이라고 하자. 각 값은 0 <= descr(r,c) <= 15를 만족한다.

descr(r,c)는 칸 (r,c)가 인접한 칸과 연결된 방향에 따라 다음과 같이 정해진다.

descr(r,c) = 0if connected((r,c), (r-1,c)): descr(r,c) += 1  # UPif connected((r,c), (r,c+1)): descr(r,c) += 2  # RIGHTif connected((r,c), (r+1,c)): descr(r,c) += 4  # DOWNif connected((r,c), (r,c-1)): descr(r,c) += 8  # LEFT

예를 들어 크기가 1인 폴리오미노의 칸은 어떤 이웃 칸과도 연결되지 않으므로 값이 0이다. 위쪽 칸과 아래쪽 칸에 모두 연결된 칸의 값은 5이다.

각 테스트 케이스마다 격자가 규칙을 만족하면 valid, 그렇지 않으면 invalid를 한 줄에 출력한다.