SRM440 div2 medium 迷路問題。

交差点を何回曲がったかを答える問題．

class MazeWanderingEasy {
public:
  int decisions(vector  maze) {
    int row = maze.size();
    int col = maze[0].length();
    pii start, goal;
    //search start and goal point
    for(int i = 0; i < row; i++) {
      for(int j = 0; j < col; j++) {
	if(maze[i][j] == 'M') {
	  start.first = i;
	  start.second = j;
	}
	if(maze[i][j] == '*') {
	  goal.first = i;
	  goal.second = j;
	}
      }
    }
    queue< pii > Q;
    int dir[4][2] ={ {-1, 0},{1, 0}, {0, 1}, {0, -1} };
    int step[row][col];
    memset(step, -1, sizeof step);
    Q.push(start);
    step[start.first][start.second] = 0;

    while( !Q.empty()) {
      pii pos = Q.front(); Q.pop();
      int x = pos.first; int y = pos.second;
      if(x == goal.first && y == goal.second) {
	return step[goal.first][goal.second];
      }
      vector< pii > tmp;
      for(int i = 0; i < 4; i++) {
	int nx = dir[i][0]+x; int ny = dir[i][1]+y;
	//within range
	if( nx >= 0 && nx < row && ny >= 0 && ny < col ) {
	    if(maze[nx][ny] != 'X' && step[nx][ny] == -1) {
	      tmp.push_back(pii(nx, ny));
	      Q.push(pii(nx, ny));
	    }
	  } //end if
	  
	  } //end for
	int cornercnt = tmp.size();
	if(cornercnt == 1) {
	  step[tmp[0].first][tmp[0].second] = step[x][y];
	} else {
	  while(cornercnt > 0) {
	    step[tmp[cornercnt-1].first][tmp[cornercnt-1].second] = step[x][y]+1;
	    cornercnt--;
	  }
	}
    }// end while
    return -1;
  }
//流れとしては、始点、終点を求める
幅優先検索で二つ以上曲がれる時一つカウントアップする．
ゴール先のstepの値がそのまま答えになる．
T字の形になっているとき、
→
00011-
--1---
--1---
-2122*
のようにする．
このとき、本当は赤色のところでカウントアップしたいが、いくつ分岐できるか分からないので、
ひとまずvectorにかくのうして、vectorのsizeにあわせてstepをそのままにするか、1だけ増やすかを決めている．

あとは迷路に深さ優先検索はやっぱり相性が相性が悪いと思うので、書く練習にはいいが実践には使わない方が良さげ．．
関数が30階くらい深くなってくるとスタックオーバーが気になる．