ACM-ICPC 2010年 国内予選 問題B 迷図と命ず

問題B:迷図と命ず

文字列をそのまま読み込んで、幅探索。

#include <iostream>
#include <complex>
#include <queue>
#include <cstring>
using namespace std;

typedef complex<int> P;

int w, h;

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int d[30*2-1][30*2-1];

int main()
{
    while (cin >> w >> h, w|h) {
        cin.ignore();

        vector<string> ss(2*h-1);
        for (int i = 0; i < 2*h-1; i++)
            getline(cin, ss[i]);

        queue<P> que;
        que.push(P(0, 0));
        memset(d, 0, sizeof(d));
        d[0][0] = 1;
        int gy = (2*h-1)-1, gx = (2*w-1)-1;
        while (que.size()) {
            P p = que.front(); que.pop();
            for (int i = 0; i < 4; i++) {
                int py = p.real(), px = p.imag();
                if (px == gx && py == gy)        goto end;

                int nx = px + dx[i];
                int ny = py + dy[i];
                if (!(0 <= nx && nx < 2*w-1))    continue;
                if (!(0 <= ny && ny < 2*h-1))    continue;
                if (ss[ny][nx] == '1')           continue;

                int tx = nx + dx[i];
                int ty = ny + dy[i];
                if (d[ty][tx] != 0)              continue;

                d[ty][tx] = d[py][px] + 1;
                que.push(P(ty, tx));
            }
        }
end:
        cout << d[gy][gx] << endl;
    }
    return 0;
}