読者です 読者をやめる 読者になる 読者になる

AOJ 1144 Curling 2.0

C/C++ AOJ Algorithms DFS

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1144&lang=jp

日本語。

解法

DFSで解く。四方向見て、進めるなら進む。盤面の外に行ったら次っていう感じでまわしてく。

コード

int w, h;
int board[20][20];
int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0};

int dfs(int y, int x, int c){
  int ret = INF;
  if(c >= 10) return ret;
  rep(d, 4){
    int ny = y+dy[d], nx = x+dx[d];
    if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue;
    if(board[ny][nx] == 1) continue;
    if(board[ny][nx] == 3) return c+1;
    while(true){
      ny += dy[d]; nx += dx[d];
      if(ny < 0 || nx < 0 || ny >= h || nx >= w) break;;
      if(board[ny][nx] == 3) return c+1;
      if(board[ny][nx] == 1){
    board[ny][nx] = 0;
    ret = min(ret, dfs(ny-dy[d], nx-dx[d], c+1));
    board[ny][nx] = 1;
    break;
      }
    }
  }
  return ret;
}

int main(){
  while(scanf("%d%d", &w, &h) && w+h){
    rep(i, h) rep(j, w) scanf("%d", &board[i][j]);
    int y, x;
    rep(i, h) rep(j, w) if(board[i][j] == 2) y = i, x = j;
    board[y][x] = 0;
    int res = dfs(y, x, 0);
    printf("%d\n", res==INF?-1:res);
  }
  return 0;
}