Problem 1166 : Amazing Mazes

Problem B: 迷図と命ず
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1166&lang=jp

• 問題概要

迷路を抜ける最短コスト。壁が与えられる。

• 解法

BFS。壁の与えられ方がめんどくさいので、おちついてテーブルつくれば問題ない。
Path on a grid
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0037&lang=jp
の壁の与え方にすごくにてた。思い出した。
わりと、すっきりとけたけど、本番でみたらけっこう焦りそうだなぁ。

• ソース

#include<iostream>
#include<queue>

using namespace std;

struct State{
  int x, y, cost;
};

main(){

  int w, h;

  while (cin >> w >> h){
    if(w + h == 0)break;

    
    bool cl[h][w], row[h][w];

    fill(&cl[0][0], &cl[h-1][w], false);
    fill(&row[0][0], &row[h-1][w], false);

    for(int i=0; i<h; i++){
      for(int j=0; j<w-1; j++){
	int tmp;
	cin >> tmp;
	if(tmp == 1){
	  cl[i][j] = true;
	}
      }
      if(i == h-1)continue;
      for(int j=0; j<w; j++){
	int tmp;
	cin >> tmp;
	if(tmp == 1){
	  row[i][j] = true;
	}
      }
    }

    State s;
    s.x = 0;
    s.y = 0;
    s.cost = 0;

    queue<State> Q;
    
    Q.push(s);
    bool visited[h][w];
    fill(&visited[0][0], &visited[h-1][w], false);
    int ans = -1;
    while(!Q.empty()){
      int tx[] = {-1, 1, 0, 0}, ty[] = {0, 0, 1, -1};
      
      s = Q.front();
      Q.pop();
      visited[s.y][s.x] = true;
      if(s.y == h-1 && s.x == w-1){
	ans = s.cost;
	break;
      }

      for(int i=0; i<4; i++){
	if(cl[s.y][s.x] && i == 1)continue;
	if(cl[s.y][s.x-1] && i == 0)continue;
	if(row[s.y][s.x] && i==2)continue;
	if(row[s.y-1][s.x] && i==3)continue; 
	int nx = s.x + tx[i], ny = s.y + ty[i];
	if(nx < 0 || ny < 0 || nx >= w || ny >= h){
	  continue;
	}

	if(visited[ny][nx])continue;
	State tmp = s;
	tmp.x = nx;
	tmp.y = ny;
	tmp.cost++;
	visited[ny][nx] = true;
	Q.push(tmp);
      }
    }
    if(ans > 0)cout << ans+1 << endl;
    else cout << 0 << endl;
  }
}
	

ちゃんとかけた。授業として前で実演でといたので、いろんなひとにソースみられながらかいた。
緊張した。