SRM 509 Div2 Hard NumberLabyrinthDiv2

問題

R*Cのグリッドで区切られたボードを(c1, r1)の座標から(c2, r2)まで移動することを考える。各セルは0~9までの数字が書いてあるかもしくはemptyを示す'.'が書いてある。数字dが書いてあるセル(x, y)からは(x - d, y)、(x + d, y)、(x, y - d)、(x, y + d)に移動できる。またemptyセルに入った場合は、０〜９までの好きな数字を選んで数字のあるセルと同じように動く、ということを最大K回行える。ゴールにたどり着くための最小の移動回数を求めよ。

やりかた

emptyセルに入った回数を記録しながら、それがKより大きくならない範囲で幅優先探索していけばいい。

以下ソース。修正前。これでも通るけど、綺麗になおしたい。

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

class NumberLabyrinthDiv2 {
public:
  int H, W;
  int dist[51][51][51];//セル(y,x)にk回のemptyセル突入後に辿り着ける最小移動回数
  bool in(int y, int x){return 0 <= y && y < H && 0 <= x && x < W;}
  int getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) {
    H = board.size();
    W = board[0].size();
    for(int i = 0; i < 50; i++) 
      for(int j = 0; j < 50; j++)
	for(int k = 0; k <= 50; k++)
	  dist[i][j][k] = INF;

    queue<pair<int, int> > Q;
    Q.push(make_pair(r1 * W + c1, 0));
    dist[r1][c1][0] = 0;
    while(!Q.empty()){
      int y = Q.front().first / W;
      int x = Q.front().first % W;
      int k = Q.front().second;
      Q.pop();

      if(y == r2 && x == c2) return dist[y][x][k];

      if(board[y][x] == '.'){
	if(k == K) continue;
	for(int i = 1; i <= 9; i++)
	  for(int j = 0; j < 4; j++){
	    int ny = y + i * dy[j];
	    int nx = x + i * dx[j];
	    if(in(ny, nx) && dist[ny][nx][k + 1] > dist[y][x][k] + 1){
	      dist[ny][nx][k + 1] = dist[y][x][k] + 1;
	      Q.push(make_pair(ny * W + nx, k + 1));
	    }
	  }
      }else{
	int d = board[y][x] - '0';
	if(d == 0) continue;
	for(int j = 0; j < 4; j++){
	  int ny = y + d * dy[j];
	  int nx = x + d * dx[j];
	  if(in(ny, nx) && dist[ny][nx][k] > dist[y][x][k] + 1){
	    dist[ny][nx][k] = dist[y][x][k] + 1;
	    Q.push(make_pair(ny * W + nx, k));
	  }
	}
      }
    }
    return -1;
  }
};

またしても最初状態をきちんと持たせないまま幅優先探索をしてしまった。引数の制約がそこまできつくないのだから状態を正確に記述できるようリッチに変数を確保するべきで、変にケチったりしないほうがいいんだ。