TopCoder SRM 509 Div2 Hard NumberLabyrinthDiv2

サクサク行きます。
http://community.topcoder.com/stat?c=problem_statement&pm=11137

問題

２次元のグリッドが与えられる。
一部のセルは数値が書かれており、残りのセルは何も書かれていない。

ここで、スタートとゴールとなるセルが指定されるので、最小コストで移動したい。
移動は以下の手順で行う。

• 数値が書かれているセルにいる場合、その数字のマス分上下左右の１方向に移動できる。この時コストが１かかる。
• 数値が書かれていないセルにいる場合、そのマスに任意の１ケタの数字を書き、上記の手順同様に移動できる。ただし、数値を書くのは全体でK回しかできない。

ゴールセルまでの移動の最小コストを求めよ。

解法

グリッドのセル(r,c)と残り数値書き換え回数(p)で状態(r,c,p)を持ち、ダイクストラの要領で最小コストを求めればよい。

r,c,p<=50だし、移動マスの候補は最大でも36(４方向に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;
	}
};

まとめ

位置に対してもう１個状態を持ってダイクストラの要領で処理する問題、
G: King's Ring Tower - Maximum-Cup 2013 | AtCoder
とかで見たね。