prithivMLmods/Coder-Stat

1 2 3 4<h1>Problem E : Connect</h1>5<p>6<i>r</i> × <i>c</i> のグリッドが与えられる。<br>7グリッドのいくつかのマスには1から8までの数字が書かれている。<br>8</p>9<p>10<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ACPC2012Day2_img_puzzle_05" height="150" witdh="150">11</p>12 13<p>14数字が書かれているマスと他の数字が書かれているマスを線で結ぶ必要がある。<br>15数字が書かれているマスについて、そのマスに書かれている本数だけ、他のマスとの間に線を結ぶ必要がある。<br>16ただし、線を結べるのは上下左右方向だけで、一つの方向について、最大２本までである。<br>17<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ACPC2012Day2_img_puzzle_06" height="150" witdh="150">18<br>19 20<br>21他の数字を跨いで線で結ぶことはできない。<br>22<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ACPC2012Day2_img_puzzle_12" height="150" witdh="150"><br>23<br>24また、次のように交差してしまう結び方をすることはできない。<br>25<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ACPC2012Day2_img_puzzle_08" height="150" witdh="150">26</p>27 28<p>29グリッドが入力として与えられるので、数字が書かれているマス全てを正しく結ぶ方法が、何通りあるのかを数えて欲しい。<br>30</p>31 32<h2>Input</h2>33<p>34入力は以下のフォーマットで与えられる。35</p>36 37<pre>38<i>r</i> <i>c</i> 39<i>grid<sub>1</sub></i>40.41.42.43<i>grid<sub>r-1</sub></i>44</pre>45 46<p>47<i>grid<sub>i</sub></i> は長さcの文字列で、1から8までの数字か"."からなる。48</p>49 50<p>51入力は以下の制約を満たす<br>521 &le; <i>r,c</i> &le; 1053</p>54 55<h2>Output</h2>56<p>57答えの値を100,000,007で割った余りを1行に出力せよ58</p>59 60<h2>Sample Input 1</h2>61<pre>623 363.1.641.165.1.66</pre>67 68<h2>Sample Output 1</h2>69<pre>70071</pre>72 73<h2>Sample Input 2</h2>74<pre>751 3761.177</pre>78 79<h2>Sample Output 2</h2>80<pre>81182</pre>83 84<h2>Sample Input 3</h2>85<pre>863 3874.288...892..90</pre>91 92<h2>Sample Output 3</h2>93<pre>94195</pre>96 97<h2>Sample Input 4</h2>98<pre>997 71002.3.1.1101.......1022......103.......104..3.3..105.......1062.2.4.3107</pre>108 109<h2>Sample Output 4</h2>110<pre>11110112</pre>113 114 115 116