No.506 限られたジャパリまん

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 43
作問者 : 0214sh70214sh7 / テスター : ixmelixmel

0 ProblemId : 1603 / 出題時の順位表

問題文

あなたは今ジャパリパークという動物園のとある「ちほー」と呼ばれるエリアにいます。
このちほーは東西方向に$H$メートル、南北方向に$W$メートルの$(H+1)*(W+1)$の格子点から構成される升目で表現され、あなたは今$(0,0)$にいます。あなたは東と北のみの移動で$(H,W)$まで行こうとしています。
このちほーの各所にはフレンズと呼ばれるヒトの姿をした動物がおり、それぞれ$N[i]$という名前で$(x[i],y[i])$にいることがわかっています。また、一箇所にいるフレンズは1体以下です。
フレンズのいる所は通ることができませんが、ジャパリまんというおまんじゅうを1つ渡すと通れるようになります。
スタートやゴールにもフレンズがいる場合はありません。
(注:当初いるという想定でしたが、実際のテストケースにはないのと事態を鑑みて、いないものとしました。)

最短で$(H,W)$まで行く経路が最も多くなるようにジャパリまんを渡すフレンズの名前を、また経路の数を$1000000007$で割った余りを出力してください。
但し、$(H,W)$までたどり着けない場合は0を出力すること。全てのテストケースはたどり着けない場合及びジャパリまんを持っていない場合を除き、最大経路となる例は一つである。

入力

$H$ $W$ $K$ $P$
$x[1]$ $y[1]$ $N[1]$
$x[2]$ $y[2]$ $N[2]$
…
$x[K]$ $y[K]$ $N[K]$

$H$はこのちほーの東西方向の長さを表しています。
$W$はこのちほーの南北方向の長eさを表しています。
$K$はこのちほーにいるフレンズの数を表しています。
$P$はあなたが持っているジャパリまんの数を表しています。
$x[i]$,$y[i]$は$i$番目のフレンズが$(x[i],y[i])$にいることを表しています。
$N[i]$は$i$番目のフレンズの名前を表しています。
$N[i]$のみ文字列で、その他はすべて整数です。

$1≤H,W≤32$
$1≤K≤min(15,H \times W - 2)$
$0≤P≤K$
$0≤x[i]≤H$
$0≤y[i]≤W$
$i≠j$のとき$(x[i],y[i])≠(x[j],y[j])$
($x$、$y$のどちらかのみが一致することはある)
$(x[i],y[i]) \ne (0,0),(H,W)$
(スタートとゴールにはフレンズはいない)
$i≠j$のとき$N[i]≠N[j]$
$N[i]$は半角英字(小文字のみ)で1文字以上10文字以内

出力

1行目に最多となる最短経路の数を$1000000007$で割った余りを出力してください。
続いてジャパリまんをあげるフレンズの名前を入力された順に改行区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
1 2 1 1
0 1 serval
出力
3
serval

◯─G
│ │
サ─◯
│ │
S─◯

サーバルちゃんにジャパリまんをあげると通れる経路が1通りから3通りに増えます。

サンプル2
入力
3 4 2 0
3 3 konoha
2 4 mimi
出力
0

ジャパリまんを持っていないため、この例ではゴールにたどり着けず0通りとなります。

サンプル3
入力
10 10 6 4
2 9 moose
1 8 chameleon
4 7 shoebill
5 8 porcupine
6 7 whiterhino
6 5 armadillo
出力
183928
shoebill
porcupine
whiterhino
armadillo

提出ページヘ