TopCoder SRM 335 Div1 Medium ExpensiveTravel

問題

hxwのグリッドが与えられる。
グリッドのそれぞれには1〜9の数字が書かれている。
このグリッドの(startRow,startCol)を出発して、(goalRow,goalCol)へ行きたい。

一回の移動では、上下左右に何回か動くことができる。
ただし、一回の移動中に通ったマス（始点と終点のマスを含む）の数字の逆数の総和が1を超えてはならない。
たとえば3→3→3のや2→4→4のようには移動できて、
2→3→4のようには移動できない。
また、1のマスには移動することができない。

このとき、ゴールのマスへ行くには最低で何回の移動が必要か、求めよ。
不可能なら-1を返せ。

制約条件

h,w≦50

方針

ダイクストラ法による。
そのマスに辿り着くコストを、(移動の回数)+(移動中のコスト)のように持っておく。
隣のマスに移動したときに、(移動中のコスト)が1を超えたら、
(移動の回数)を+1して、移動中のコストは最初の一歩分だけにする。

すると、この比較でコストに対して全順序が決められるので、
ダイクストラ法を使って探索することができる。

実際には移動中のコストはGCD{1〜9}=2520までの数字として持っておく。

ソースコード

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
bool v[50][50];

class ExpensiveTravel {
	public:
	int minTime(vector <string> m, int sy, int sx, int gy, int gx) 
	{
		sy--; sx--;
		gy--; gx--;
		if(sy==gy&&sx==gx)return 0;
		if(m[sy][sx]=='1')return -1;
		
		int h=m.size(), w=m[0].size();
		
		priority_queue<pi> q;
		q.push(mp(-2520/(m[sy][sx]-'0'),sy*w+sx));
		memset(v,0,sizeof(v));
		
		while(!q.empty()){
			int y=q.top().second/w, x=q.top().second%w;
			int cost=-q.top().first; q.pop();
			int step=cost/2521, t=cost%2521;
			
			if(v[y][x])continue;
			v[y][x]=1;
			if(y==gy&&x==gx)return step+1;
			
			rep(d,4){
				int ny=y+dy[d], nx=x+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w)continue;
				if(v[ny][nx]||m[ny][nx]=='1')continue;
				
				int t1=2520/(m[y][x]-'0'), t2=2520/(m[ny][nx]-'0');
				if(t+t2>2520)q.push(mp(-(step+1)*2521-t1-t2,ny*w+nx));
				else q.push(mp(-step*2521-t-t2,ny*w+nx));
			}
		}
		return -1;
	}
};