C(O|W|A*RD*|S)* 크로스워드 퍼즐

1913년 12월 21일 아서 윈이 최초의 크로스워드 퍼즐을 발표했다. 고조부의 발명 100주년을 기념하려고 존 "겁쟁이" 윈이 직접 크로스워드 퍼즐을 만들기 시작했지만 좀처럼 진도가 나가지 않았다. 그는 워낙 겁이 많아서, 어떤 단어에 재치 있는 단서를 떠올릴 때마다 그 단서로는 그 단어를 가리킬 수 없다는 비난을 받을까 봐 걱정을 멈추지 못했다. 결국 날마다 겁을 먹고 지루한 단서를 골랐고, 퍼즐도 그만큼 시시해졌다.

어느 날 그는 더 나은 생각을 떠올렸다. 단어의 뜻이 전혀 중요하지 않은데도 재미있는 퍼즐이다. 동료들에게 이야기하니 모두 흥미로운 발상이라고 인정했고, 그의 별명을 따서 이 퍼즐을 겁쟁이의 크로스워드 퍼즐이라고 불렀다.

그런데 겁쟁이의 크로스워드 퍼즐을 만드는 일은 쉽지 않았다. 단어의 뜻은 신경 쓰지 않아도 되지만, 퍼즐의 답이 오직 하나인지 확인하는 일은 여전히 까다로웠다. 100주년이 다가오자 존은 재미있는 퍼즐을 제때 완성하지 못할까 걱정하기 시작했다. 겁쟁이의 크로스워드 퍼즐을 푸는 프로그램을 작성해서 존을 돕자.

퍼즐 하나는 h × w개의 칸과 가로 단서 h개, 세로 단서 w개로 이루어진다. i번째 가로 단서는 i번 행을 왼쪽에서 오른쪽으로 읽은 단어와 일치해야 하고, j번째 세로 단서는 j번 열을 위에서 아래로 읽은 단어와 일치해야 한다. 모든 단서는 아래 BNF 문법으로 정의한 패턴 언어로 쓴 정규 표현식이다.

clue       ::= "^" pattern "$"
pattern    ::= simple | pattern "|" simple
simple     ::= basic | simple basic
basic      ::= elementary | elementary "*"
elementary ::= "." | "A" | "B" | ... | "Z" | "(" pattern ")"

패턴 언어의 BNF 문법.

단서 p와 q가 단어 s와 일치하는 규칙은 다음과 같다.

• p가 s와 일치하면 ^p$가 s와 일치한다.
• p와 q 중 적어도 하나가 s와 일치하면 p|q가 s와 일치한다.
• s1s2 = s이고 p가 s1과 일치하며 q가 s2와 일치하는 s1, s2가 있으면 pq가 s와 일치한다.
• s가 빈 문자열이거나, s1s2 = s이고 p가 s1과 일치하며 p*가 s2와 일치하는 s1, s2가 있으면 p*가 s와 일치한다.
• A, B, ..., Z는 각각 그 문자 자신과 일치한다.
• p가 s와 일치하면 (p)가 s와 일치한다.
• .은 (A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)를 줄여 쓴 것이다.

아래 그림은 답을 칸에 채워 넣은 겁쟁이의 크로스워드 퍼즐이다.

Java: 제출하는 Java 프로그램은 java.util.regex 패키지의 클래스를 사용할 수 없다.

C++: 제출하는 C++ 프로그램은 std::regex 클래스를 사용할 수 없다.

이 문제에 등장하는 인물 가운데 아서 윈을 뺀 나머지는 모두 가상이다. 실제 인물과 닮은 점이 있어도 우연이다.

입력은 여러 개의 데이터 집합으로 이루어지고, 각 데이터 집합은 퍼즐 하나를 다음 형식으로 나타낸다.

h w
p1
p2
.
.
.
ph
q1
q2
.
.
.
qw

h와 w는 각각 칸의 세로 개수와 가로 개수이며 2 ≤ h, w ≤ 4이다. pi는 i번 행의 가로 단서, qj는 j번 열의 세로 단서다. 단서의 길이는 512자를 넘지 않는다.

마지막 데이터 집합 다음에는 0이 두 개 적힌 줄이 온다. 데이터 집합은 30개를 넘지 않는다.

각 데이터 집합마다 퍼즐의 답이 오직 하나면 w개 문자로 이루어진 h개 줄로 출력한다. 답이 없으면 none을, 답이 둘 이상이면 ambiguous를 출력한다.