ACM-ICPC 2010 国内予選問題 Problem B 迷図と命ず
Problem B 迷図と命ず
幅優先探索。こういう入力の時は文字列のまま持っておくと楽らしい。
#include <iostream> #include <vector> #include <string> using namespace std; int main() { const int dirx[4] = { 1, 0, -1, 0 }; const int diry[4] = { 0, 1, 0, -1 }; while ( true ) { int w, h; cin >> w >> h; if ( w == 0 && h == 0 ) break; vector<string> wall(2*h-1); cin.ignore(); for ( int i=0; i<2*h-1; i++ ) getline( cin, wall[i] ); vector<vector<int> > dist( h, vector<int>( w, 0 ) ); dist[0][0] = 1; for ( int d=1; d<w*h; d++ ) { for ( int y=0; y<h; y++ ) for ( int x=0; x<w; x++ ) if ( dist[y][x] == d ) for ( int r=0; r<4; r++ ) { int tx = x + dirx[r]; int ty = y + diry[r]; if ( 0 <= tx && tx < w && 0 <= ty && ty < h && wall[ty+y][tx+x] == '0' && dist[ty][tx] == 0 ) dist[ty][tx] = d + 1; } } cout << dist[h-1][w-1] << endl; } }