サクサク行きます。
http://community.topcoder.com/stat?c=problem_statement&pm=11137
問題
2次元のグリッドが与えられる。
一部のセルは数値が書かれており、残りのセルは何も書かれていない。
ここで、スタートとゴールとなるセルが指定されるので、最小コストで移動したい。
移動は以下の手順で行う。
- 数値が書かれているセルにいる場合、その数字のマス分上下左右の1方向に移動できる。この時コストが1かかる。
- 数値が書かれていないセルにいる場合、そのマスに任意の1ケタの数字を書き、上記の手順同様に移動できる。ただし、数値を書くのは全体でK回しかできない。
ゴールセルまでの移動の最小コストを求めよ。
解法
グリッドのセル(r,c)と残り数値書き換え回数(p)で状態(r,c,p)を持ち、ダイクストラの要領で最小コストを求めればよい。
r,c,p<=50だし、移動マスの候補は最大でも36(4方向に1~9マス移動)しかないので計算量は問題ない。
int cost[64][64][64]; class NumberLabyrinthDiv2 { int R,C; public: int getMinimumNumberOfMoves(vector <string> board, int r1, int c1, int r2, int c2, int K) { int x,y,z,d,i; R=board.size(); C=board[0].size(); FOR(x,64) FOR(y,64) FOR(z,64) cost[x][y][z]=10000; cost[r1][c1][K]=0; queue<int> Q; Q.push(r1*10000+c1*100+K); while(!Q.empty()) { int k=Q.front(); Q.pop(); int cy=k/10000,cx=(k/100)%100,ck=k%100; for(d=1;d<=9;d++) { if(board[cy][cx]!='.' && board[cy][cx]!='0'+d) continue; if(board[cy][cx]=='.' && ck==0) continue; FOR(i,4) { int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; int ty=cy+dy[i]*d,tx=cx+dx[i]*d; if(tx<0 || tx>=C || ty<0 || ty>=R) continue; if(cost[ty][tx][ck-(board[cy][cx]=='.')] > cost[cy][cx][ck]+1) { cost[ty][tx][ck-(board[cy][cx]=='.')] = cost[cy][cx][ck]+1; Q.push(ty*10000+tx*100+ck-(board[cy][cx]=='.')); } } } } int mi=10000; FOR(i,K+1) mi=min(mi,cost[r2][c2][i]); if(mi>=10000) return -1; return mi; } };
まとめ
位置に対してもう1個状態を持ってダイクストラの要領で処理する問題、
G: King's Ring Tower - Maximum-Cup 2013 | AtCoder
とかで見たね。