3009:Curling 2.0

keyword

探索　C++

概要

2次元のボード上に石がいくつかある。この上でカーリングをして滑るヤツを目的地に持っていきたい。滑るヤツは石に当たるまで止まらないし、石に当たるとぶつかった石を破壊する。最短で何回滑らせれば良いか求める問題。ただし10回以上滑らせてはいけない。
実装ゲー。最大計算量もたかが知れているので愚直に探索すればよい。

char board[22][22];
int sx, sy, gx, gy;
int n, m;
int dx[] = {0,0,1,-1}, dy[] = {1,-1,0,0};

inline int dfs(int y, int x, int depth){
    if(depth >= 10) return 1<<10;
    int k, nx, ny, ans = 1<<10;
    REP(k,4){
        ny = y + dy[k];
        nx = x + dx[k];
        if(board[ny][nx] == 1) continue;
        while(!board[ny][nx]){
            ny += dy[k];
            nx += dx[k];
        }
        if(board[ny][nx] == 3) return depth+1;
        if(board[ny][nx] == 1){
            board[ny][nx] = 0;
            ans = min(ans, dfs(ny-dy[k],nx-dx[k],depth+1));
            board[ny][nx] = 1;
        }
    }
    return ans;
}

int main(){
    int i, j;
    while(m = readint(), n = readint(), n){
        REP(i,n+2)REP(j,m+2) board[i][j] = 4;
        FOR(i,1,n+1)FOR(j,1,m+1){
            board[i][j] = readint();
            if(board[i][j] == 2){
                sy = i, sx = j;
                board[i][j] = 0;
            }
            if(board[i][j] == 3){
                gy = i, gx = j;
            }
        }
        int ans = dfs(sy,sx,0);
        printf("%d\n",ans<=10?ans:-1);
    }

    return 0;
}