Problem:


MathJax.Hub.Config({
  tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}
});

Alternate Escape

アリスハウス

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

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

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

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

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

Input

入力は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個の整数 Horzi,1, Horzi,2, ..., Horzi,Wを含む．
Horzi,jは，i 行 j 列目のマスの上側の辺に壁が有るとき1で，無いとき0である．
ただし，HorzH+1,jは， H 行 j 列目のマスの下側の辺における壁の有無を表す．

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

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

Output

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

Sample Input

3 3 2 2
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
3 3 2 2
 1 0 1
1 0 1 1
 1 0 0
0 0 0 0
 0 0 1
1 1 0 1
 1 0 1
1 3 1 1
 1 1 1
1 0 0 1
 1 0 1
2 2 1 1
 1 0
1 0 0
 0 0
0 0 0
 0 0
0 0 0 0

Output for Sample Input

Yes
No
Yes
No

Hint

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

 初期状態

 Aliceがコマを左に動かす

 Bobは脱出を阻止するために壁を反転させる

 Aliceがコマを上に動かす

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



Sample input:
3 3 2 2
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
0 0 0 0
 1 1 1
3 3 2 2
 1 0 1
1 0 1 1
 1 0 0
0 0 0 0
 0 0 1
1 1 0 1
 1 0 1
1 3 1 1
 1 1 1
1 0 0 1
 1 0 1
2 2 1 1
 1 0
1 0 0
 0 0
0 0 0
 0 0
0 0 0 0


Sample output:
Yes
No
Yes
No

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    H, W, R, C = map(int, readline().split()); R -= 1; C -= 1
    if H == W == 0:
        return False
    G0 = [[] for i in range(H*W+1)]
    G1 = [[] for i in range(H*W+1)]
    g = H*W
    for i in range(H):
        *s, = map(int, readline().split())
        k = W*i
        if i:
            for j in range(W):
                if s[j]:
                    G1[k+j].append(k+j-W)
                    G1[k+j-W].append(k+j)
                else:
                    G0[k+j].append(k+j-W)
                    G0[k+j-W].append(k+j)
        else:
            for j in range(W):
                if s[j]:
                    G1[j].append(g)
                    G1[g].append(j)
                else:
                    G0[j].append(g)
                    G0[g].append(j)
        *s, = map(int, readline().split())
        for j in range(W-1):
            if s[j+1]:
                G1[k+j].append(k+j+1)
                G1[k+j+1].append(k+j)
            else:
                G0[k+j].append(k+j+1)
                G0[k+j+1].append(k+j)
        if s[0]:
            G1[k].append(g)
            G1[g].append(k)
        else:
            G0[k].append(g)
            G0[g].append(k)
        if s[W]:
            G1[k+W-1].append(g)
            G1[g].append(k+W-1)
        else:
            G0[k+W-1].append(g)
            G0[g].append(k+W-1)
    *s, = map(int, readline().split())
    k = (H-1)*W
    for j in range(W):
        if s[j]:
            G1[k+j].append(g)
            G1[g].append(k+j)
        else:
            G0[k+j].append(g)
            G0[g].append(k+j)

    u0 = [0]*(H*W+1)
    u1 = [0]*(H*W+1)
    u0[g] = u1[g] = 1
    que = deque([g])
    while que:
        v = que.popleft()
        for w in G0[v]:
            if u0[w]:
                continue
            if u1[w]:
                que.append(w)
            u0[w] = 1
        for w in G1[v]:
            if u1[w]:
                continue
            if u0[w]:
                que.append(w)
            u1[w] = 1
    if u0[R*W + C]:
        write("Yes\n")
    else:
        write("No\n")
    return True
while solve():
    ...