ICPC 国内予選 2010 B - 迷図と命ず

以前バグらせてしまったので自戒の意も込めて

judge.u-aizu.ac.jp

問題概要

迷路の地図が与えられるので、左上から右下までの最短路を求めてほしい。
入力の与えられ方が特殊で、奇数行目には縦向きの壁、偶数行目には横向きの壁が与えられる。
詳しくは上記のリンクをクリックすれば、入力例に図がついていて分かりやすい。

考えたこと

迷路の最短路なので考えるまでもなくBFSなのだが、厄介なのは入力の受け取り方である。
入力を取得したのち上手い具合に典型に落とし込もうとも考えたが結局実装が大変になる。
そこで、探索を行いながら、縦方向、横方向の移動に場合分けをして、それぞれ移動可能かを調べることにした。

解法

0-indexなので偶数行目の場合は縦向きの壁が与えられ、奇数行目には横向きの壁が与えられる。
横軸移動の場合にぶつかる可能性のある壁、即ち偶数行目の入力を配列hx、奇数行目の配列を配列hyに入れていき、それぞれ移動時に壁にぶつかるか判定する。
ここで注意しなければならないのが、負の方向へ移動する場合である。
例えば、x座標を0->1に移動する場合、hx[0](つまり、移動前のx座標に壁があるかどうか)を調べればそれで良いが、1->0移動の場合もhx[0]を参照しなければならないのである。

図がめちゃくちゃ雑で恐縮だが、つまりこういうことである。
実際には壁は0と1の間にあるが、hx[0.5]と表現することは不可能(配列を使わなければ可能だが)なので、壁の位置はhx[0]となる。
よって、hx,hyのindexは、正の方向に移動する場合は移動前の座標、負の方向に移動する場合は移動後の座標ということになる。私はこれに気づかず時間を溶かした。
今回は移動を先に行うため、負の方向に移動した場合は現在（移動後）の座標、正の方向に移動した場合は移動前の座標をindexに使っている。

実装は以下のとおりである。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
typedef pair<int,int> P;
#define INF 1e9

int main(){
    int h,w;
	while(cin>>w>>h){
        if(w==0)break;
        int kx[h][w-1];
        int ky[h-1][w];
        int c=0,cc=0;
        memset(kx,0,sizeof(kx));
        memset(ky,0,sizeof(ky));
        for(int i=0;i<2*h-1;i++){
            if(i%2==0){
                for(int j=0;j<w-1;j++){
                    cin>>kx[c][j];
                }
                c++;
            }else{
                for(int j=0;j<w;j++){
                    cin>>ky[cc][j];
               }
                cc++;
            }
        }
        int d[31][31];
        for(int i=0;i<31;i++)for(int j=0;j<31;j++)d[i][j]=INF;
        int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
        int sx=0,sy=0,gx=w-1,gy=h-1;
        queue<P> que;
        que.push(P(sy,sx));
        d[sy][sx]=0;
        while(que.size()){
            P p = que.front(); que.pop();
            if(p.first==gy&&p.second==gx)break;
            for(int i=0;i<4;i++){
                int ny = p.first + dy[i], nx = p.second + dx[i];
                int tmp=0;

                //移動時、壁の位置調整
                //負の方向に移動する場合、移動先の座標を参照する
                //今回は移動が先に行われているので、正の方向に移動するときに、移動前の座標を取得したい
                if(dx[i]==-1||dy[i]==-1){
                    if(dx[i])tmp = 0;
                    else tmp = 0;
                }else{
                    if(dx[i])tmp = dx[i];
                    else tmp = dy[i];
                }

                //壁の判定
                if(dx[i]!=0&&kx[ny][nx-tmp]==1){
                    continue;
                }
                if(dy[i]!=0&&ky[ny-tmp][nx]==1){
                    continue;
                }

                if(nx>=0&&nx<w&&0<=ny&&ny<h&&d[ny][nx]==INF){
                    que.push(P(ny,nx));
                    d[ny][nx] = d[p.first][p.second] + 1;
                }
            }
        }

        // for(int i=0;i<h;i++){
        //     for(int j=0;j<w;j++){
        //         cout<<d[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }

        if(d[gy][gx]==INF)d[gy][gx]=0;
        else d[gy][gx]++;
        cout<<d[gy][gx]<<endl;
    }
}