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

B. 迷図と命ず

解法

• 入口から幅優先探索
• データが綺麗に成形してあるので、文字列のまま持っておくと楽
  • 座標を2倍すると文字列上での現在地に対応する

#include <iostream>
#include <queue>

using namespace std;

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

int main(){
    int w, h;
    string s[59];
    int step[30][30];
    while(cin >> w >> h, w){
        getline(cin, s[0]);
        for(int i=0;i<2*h-1;i++) getline(cin, s[i]);
        for(int i=0;i<2*h-1;i++) s[i] += " ";
        memset(step, -1, sizeof(step));
        queue< pair<int, int> > qu; qu.push(make_pair(0,0));
        step[0][0] = 1;
        while(!qu.empty()){
            pair<int, int> p = qu.front(); qu.pop();
            int x = p.first, y = p.second;
            for(int i=0;i<4;i++){
                int nx = x+dx[i], ny = y+dy[i];
                if(nx<0||h<=nx||ny<0||w<=ny) continue;
                if(s[2*x+dx[i]][2*y+dy[i]]=='1') continue;
                if(step[nx][ny]!=-1) continue;
                step[nx][ny] = step[x][y] + 1;
                qu.push(make_pair(nx, ny));
            }
        }
        cout << (step[h-1][w-1] == -1 ? 0 : step[h-1][w-1]) << endl;
    }
}