prithivMLmods/Coder-Stat

1 2 3<H1><font color="#000">Problem J: </font><span>C(O|W|A*RD*|S)* CROSSWORD</span> Puzzle</H1>4 5<p>6The first crossword puzzle was published on December 21, 1913 by Arthur Wynne. To celebrate the centennial of his great-great-grandfather's invention, John "Coward" Wynne<sup>1</sup> was struggling to make crossword puzzles. He was such a coward that whenever he thought of a tricky clue for a word, he couldn’t stop worrying if people would blame him for choosing a bad clue that could never mean that word. At the end of the day, he cowardly chose boring clues, which made his puzzles less interesting.7</p>8 9<p>10One day, he came up with a brilliant idea: puzzles in which word meanings do not matter, and yet interesting. He told his idea to his colleagues, who admitted that the idea was intriguing. They even named his puzzles "Coward's Crossword Puzzles" after his nickname. 11</p>12 13<p>14However, making a Coward's crossword puzzle was not easy. Even though he did not have to think about word meanings, it was not easy to check if a puzzle has one and only one set of answers. As the day of the centennial anniversary was approaching, John started worrying if he would not be able to make interesting ones in time. Let's help John by writing a program that solves Coward's crossword puzzles.15</p>16 17<p>18Each puzzle consists of <var>h</var> &times; <var>w</var> cells along with <var>h</var> across clues and <var>w</var> down clues. The clues are regular expressions written in a pattern language whose BNF syntax is given as in the table below.19</p>20 21<pre>22clue       ::= "^" pattern "$"23pattern    ::= simple | pattern "|" simple24simple     ::= basic | simple basic25basic      ::= elementary | elementary "*"26elementary ::= "." | "A" | "B" | ... | "Z" | "(" pattern ")"27</pre>28<center>29<span>30Table J.1. BNF syntax of the pattern language.31</span>32</center>33</br>34 35<p>36The clues (as denoted by p and q below) match words (as denoted by s below) according to the37following rules.38</p>39 40<ul>41<li><span>^</span><var>p</var><span>$</span> matches <var>s</var> if <var>p</var> matches <var>s</var>.</li>42<li><var>p</var><span>|</span><var>q</var> matches a string <var>s</var> if <var>p</var> and/or <var>q</var> matches <var>s</var>.</li>43<li><var>pq</var> matches a string <var>s</var> if there exist <var>s<sub>1</sub></var> and <var>s<sub>2</sub></var> such that <var>s<sub>1</sub>s<sub>2</sub></var> = <var>s</var>, <var>p</var> matches <var>s<sub>1</sub></var>, and <var>q</var> matches <var>s<sub>2</sub></var>.</li>44<li><var>p</var><span>*</span> matches a string <var>s</var> if <var>s</var> is empty, or there exist <var>s<sub>1</sub></var> and <var>s<sub>2</sub></var> such that <var>s<sub>1</sub>s<sub>2</sub></var> = <var>s</var>, <var>p</var> matches</li>45<li><var>s<sub>1</sub></var>, and <var>p</var><span>*</span> matches <var>s<sub>2</sub></var>.</li>46<li>Each of <span>A</span>, <span>B</span>, . . . , <span>Z</span> matches the respective letter itself.</li>47<li><span>(</span><var>p</var><span>)</span> matches <var>s</var> if <var>p</var> matches <var>s</var>.</li>48<li><span>.</span> is the shorthand of <span>(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)</span>.</li>49</ul>50 51<p>52Below is an example of a Coward’s crossword puzzle with the answers filled in the cells.53</p>54 55<center>56<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_crosswordPuzzle" style="aling:center;width:240px"><br/>57</center>58<br/>59 60<p>61<b>Java Specific:</b> Submitted Java programs may not use classes in the java.util.regex package.<br/>62<b>C++ Specific:</b> Submitted C++ programs may not use the std::regex class.63</p>64 65 66 67<H2>Input</H2>68 69<p>70The input consists of multiple datasets, each of which represents a puzzle given in the following format.71</p>72 73<pre>74<var>h</var> <var>w</var>75<var>p<sub>1</sub></var>76<var>p<sub>2</sub></var>77...78<var>p<sub>h</sub></var>79<var>q<sub>1</sub></var>80<var>q<sub>2</sub></var>81...82<var>q<sub>2</sub></var>83</pre>84 85<p>86Here, <var>h</var> and <var>w</var> represent the vertical and horizontal numbers of cells, respectively, where 2 &le; <var>h,w</var> &le; 4. The <var>p<sub>i</sub></var> and <var>q<sub>j</sub></var> are the across and down clues for the <var>i</var>-th row and <var>j</var>-th column, respectively. Any clue has no more than 512 characters.87</p>88<p>89The last dataset is followed by a line of two zeros. You may assume that there are no more than 30 datasets in the input.90</p>91 92 93<H2>Output</H2>94 95<p>96For each dataset, when the puzzle has a unique set of answers, output it as <var>h</var> lines of <var>w</var> characters. When the puzzle has no set of answers, or more than one set of answers, output "<span>none</span>" or "<span>ambiguous</span>" without double quotations, respectively.97</p>98 99<H2>Sample Input</H2>100<pre>1012 2102^(C|I|T|Y)*<span>$</span>103^(C|O|P|S)*<span>$</span>104^(F|L|I|P)*<span>$</span>105^(B|A|C|K)*<span>$</span>1062 2107^HE|LL|O*<span>$</span>108^(P|L|E|A|S|E)*<span>$</span>109^(H|L)*<span>$</span>110^EP|IP|EF<span>$</span>1114 4112^LONG|TALL|S*ALLY<span>$</span>113^(R*EV*|OL*U(TIO)*N)*<span>$</span>114^(STRAWBERRY|F*I*E*L*D*S*|FOREVER)*<span>$</span>115^P.S.|I|LOVE|YOU<span>$</span>116^(RE|A|L)((L|OV*E)*)<span>$</span>117^(LUC*Y*|IN.THE.SKY)(WITH|DI*A*M*ON*D*S*)<span>$</span>118^(IVE*|GOT|A|F*E*E*L*I*N*G*)*<span>$</span>119^YEST*E*R*D*A*Y*<span>$</span>1202 3121^(C|P)(OL|AS)<span>$</span>122^(LU|TO)(X|R)<span>$</span>123^CT|PL<span>$</span>124^OU|AO<span>$</span>125^SR|LX<span>$</span>1262 2127^T*|(HI)|S*<span>$</span>128^SE|NT|EN|CE<span>$</span>129^IS<span>$</span>130^(F|A|L|S|E)*<span>$</span>1312 4132^ARKA|BARB|COLU<span>$</span>133^NSAS|ADOS|MBIA<span>$</span>134^..<span>$</span>135^..<span>$</span>136^KA|RO|LI<span>$</span>137^AS|BA|US<span>$</span>1380 0139</pre>140 141<H2>Output for the Sample Input</H2>142<pre>143IC144PC145HE146LP147ALLY148OUNE149EDIS150LOVE151ambiguous152none153ARKA154NSAS155</pre>156 157<h2>Notes</h2>158<p>159<sup>1</sup> All characters appearing in this problem, except for Arthur Wynne, are fictitious. Any resemblance to real persons, living or dead, is purely coincidental.160</p>