22424번 - Alternate Escape 다국어

AliceとBobはボードゲームで遊んでいる． このボードゲームは， H 行 W 列のマス目が書かれた盤面と1つのコマを使って遊ぶ． このゲームでは，盤面の左上のマスを1行1列目として，下方向に行を，右方向に列を数える．

マス同士が隣接する辺と，マスが盤面の外側と接する辺には壁を置けるようになっていて，ゲームの開始時にはそれぞれの辺について壁の有無が指定されている．また，ゲームの開始時には，コマが盤面のマスのいずれか1箇所に置かれている．

AliceとBobは交互に手番をこなすことでゲームを進める． ゲームはAliceの手番から始まる． Aliceの目的は，コマを盤面の外まで動かして，迷路から脱出させることである． Aliceが1手でできる行動は，コマを今ある位置のマスから，上下左右に隣接するマスのうち，間の辺に壁がない方向のいずれかに移動させることである． コマの今あるマスが盤面の外側に接していて，間の辺に壁がない場合，そこからコマを脱出させることができる．

一方，Bobの目的は，コマの脱出を妨害することである． Bobの手番では，壁の有無を反転させるか，何もせずに手番を終えるかを選ぶことができる． 壁の有無を反転させることを選んだ場合，盤面のすべてのマスの辺について，壁の有無が反転する．

盤面の初期状態と，コマの初期位置が与えられるので，AliceとBobの両者が最適な行動をとったときに，Aliceがコマを盤面から脱出させられるか判定せよ． ただし，Aliceの手番においてコマが4方向とも壁で囲まれてしまった場合は脱出できないとみなす．

入力は40個以下のデータセットからなる． それぞれのデータセットは次の形式で与えられる．

H W R C
 Horz1,1 Horz1,2 ... Horz1,W
Vert1,1 Vert1,2 ... Vert1,W+1
...
VertH,1 VertH,2 ... VertH,W+1
 HorzH+1,1 HorzH+1,2 ... HorzH+1,W

1行目には4つの整数 H, W (1 ≤ H, W ≤ 500), R, C (1 ≤ R ≤ H, 1 ≤ C ≤ W) が与えられる． これらは盤面が H 行 W 列のマス目からなり，コマの初期位置が R 行 C 列目であることを表す．

続く 2H + 1 行には盤面の初期状態が与えられる．

2i 行目 (1 ≤ i ≤ H + 1) は，W個の整数 Horz_i,1, Horz_i,2, ..., Horz_i,Wを含む． Horz_i,jは，i 行 j 列目のマスの上側の辺に壁が有るとき1で，無いとき0である． ただし，Horz_H+1,jは， H 行 j 列目のマスの下側の辺における壁の有無を表す．

2i + 1 行目 (1 ≤ i ≤ H) は，W + 1 個の整数 Vert_i,1, Vert_i,2, ..., Vert_i,W+1を含む． Vert_i,jは， i 行 j 列目のマスの左側の辺に壁が有るとき1で，無いとき0である． ただし，Vert_i,W+1は， i 行 W 列目のマスの右側の辺における壁の有無を表す．

入力の終わりは，4つのゼロからなる1行で示される．

それぞれのデータセットについて，Aliceがコマを盤面から脱出させられる場合は"Yes"，できない場合は"No"と1行に出力せよ．

1つ目のデータセットではAliceは次のように動くことでコマを脱出させられる。

1. 初期状態
2. Aliceがコマを左に動かす
3. Bobは脱出を阻止するために壁を反転させる
4. Aliceがコマを上に動かす

Bobが次の手番で壁の有無を反転させてもさせなくても、 Aliceは次の手番でコマを脱出させられる。