roiti46's blog

主に競プロ問題の解説を載せてます

AOJ 2153: Mirror Cave

Pythonじゃ厳しいかなと思ったら案の定だった。

問題はこちら

問題

2つのWxHの部屋がある。各部屋にはゴールが設定されており、いくつか壁がある場合もある。2人が各部屋に入り、それぞれのスタート地点から同時にゴールにたどりつけるかどうかを考える。ただし、二人の移動の仕方は左右対称で、片方が右に移動したら片方は左に移動しなければならない。しかし、移動先に壁がある場合は移動せずにその場で待機することも可能である。また片方が先にゴールに到達してしまったら失敗とする。果たして2人は同時にゴールに到達できるかどうか答えよ。

解法

それぞれの座標を抱えてBFSをすればいい。2人をそれぞれA,Bとしたとき、visited[Aの座標][Bの座標]で訪れた場所を管理し、同じ座標の組み合わせを訪れないようにして重複を省く。計算量の上限はvisitedの最大サイズ504 = 6250000となる。Pythonだとこの解法では間に合わなかった。

#include <iostream>
#include <deque>
#define rep(i,a) for (int i = 0; i < (a); i++)
using namespace std;
 
int W, H, wl, hl, wr, hr, dw, dh;
int nwl, nhl, nwr, nhr, wlg, hlg, wrg, hrg;
int dws[] = {1,0,-1,0}, dhs[] = {0,1,0,-1};
char A[51][51], B[51][51];
bool visited[51][51][51][51];
 
struct Array {
    int wl, hl, wr, hr;
    Array(int wl0, int hl0, int wr0, int hr0) {
        wl = wl0, hl = hl0;
        wr = wr0, hr = hr0;
    }
};
         
 
int main(void){
    while (cin >> W >> H, W) {
        rep(h, H) {
            rep(w, W) cin >> A[h][w];
            rep(w, W) cin >> B[h][w];
        }
        rep(h, H) {
            rep(w, W) {
                if (A[h][w] == 'L') wl  = w, hl  = h;
                if (B[h][w] == 'R') wr  = w, hr  = h;
                if (A[h][w] == '%') wlg = w, hlg = h;
                if (B[h][w] == '%') wrg = w, hrg = h;
            }
        }
 
        rep(i, H) rep(j, W) rep(k, H) rep(l, W) visited[i][j][k][l] = false;
        visited[hl][wl][hr][wr] = true;
        bool flag = false;
        deque<Array> que;
        que.push_back(Array(wl,hl,wr,hr));
        while (!que.empty()) {
            Array tmp = que.front(); que.pop_front();
            wl = tmp.wl, hl = tmp.hl;
            wr = tmp.wr, hr = tmp.hr;
            if (wl == wlg && hl == hlg && wr == wrg && hr == hrg) {
                cout << "Yes" << endl;
                flag = true;
                break;
            }
             
            rep(i, 4) {
                dw = dws[i], dh = dhs[i];
                nwl = min(W-1,max(0,wl+dw)), nhl = min(H-1,max(0,hl+dh));
                if (A[nhl][nwl] == '#') nwl = wl, nhl = hl;
                nwr = min(W-1,max(0,wr-dw)), nhr = min(H-1,max(0,hr+dh));
                if (B[nhr][nwr] == '#') nwr = wr, nhr = hr;
                 
                if (!visited[nhl][nwl][nhr][nwr]) {
                    if ((nwl == wlg && nhl == hlg) ^ (nwr == wrg && nhr == hrg)) continue;
                    visited[nhl][nwl][nhr][nwr] = true;
                    que.push_back(Array(nwl,nhl,nwr,nhr));
                }
            }
        }
        if (!flag) cout << "No" << endl;
    }
    return 0;
}

以下はPythonでの同様の解答。こちらの方がアルゴリズムがどうなっているかわかりやすいと思う。C++のものとやっていることはほとんど同じだが、TLEとなってしまうのがPythonのつらいところ。

from collections import deque
dwh = zip([1,0,-1,0,],[0,1,0,-1])
while 1:
    W,H = map(int,raw_input().split())
    if W == 0: break
    A,B = [],[]
    for loop in xrange(H):
        a,b = raw_input().split()
        A.append(list(a))
        B.append(list(b))
 
    for h in xrange(H):
        for w in xrange(W):
            if A[h][w] == "L": wl ,hl  = w,h
            if B[h][w] == "R": wr ,hr  = w,h
            if A[h][w] == "%": wlg,hlg = w,h
            if B[h][w] == "%": wrg,hrg = w,h
 
    visited = [[[[False]*W for i in xrange(H)] for j in xrange(W)] for k in xrange(H)]    
    visited[hl][wl][hr][wr] = True
    que = deque([[wl,hl,wr,hr]])
    while que:
        wl,hl,wr,hr = que.popleft()
        if (wl,hl) == (wlg,hlg) and (wr,hr) == (wrg,hrg):
            print "Yes"
            break
        for dw,dh in dwh:
            nwl,nhl = min(W-1,max(0,wl+dw)), min(H-1,max(0,hl+dh))
            if A[nhl][nwl] == "#": nwl,nhl = wl,hl
            nwr,nhr = min(W-1,max(0,wr-dw)), min(H-1,max(0,hr+dh))
            if B[nhr][nwr] == "#": nwr,nhr = wr,hr
            if not visited[nhl][nwl][nhr][nwr]:
                if ((nwl,nhl) == (wlg,hlg)) + ((nwr,nhr) == (wrg,hrg)) == 1: continue
                visited[nhl][nwl][nhr][nwr] = True
                que.append([nwl,nhl,nwr,nhr])
    else:
        print "No"