TopCoder SRM 506 Div2 Hard SlimeXResidentSlime

最近ここに書いていませんが、一応Div2 HardはSRM500までは解きました。今回は割と楽。
http://community.topcoder.com/stat?c=problem_statement&pm=11268

問題

2次元のグリッドが与えられている。
通常の移動可能マス・移動不可能マスに加え、一部の移動可能マスには数字が書かれている。
このグリッド上を時間１に対し1マスのペースで隣接マスを移動できるものとする。

ある数字のマスを通過すると、その後数字の示す時間分だけそのマスは有効となる。
全部の数字マスを有効にした状態にできるか、できるなら最短時間を答えよ。

まとめ

数字マスの数字は最大９である。
よって、数字マスは11マス以上ある場合は全マスを有効にできない。

逆に数字マスは高々10個しかないため、next_permutationで移動順を全列挙し、最短経路を求めればよい。

class SlimeXResidentSlime {
	public:
	int R,C;
	vector<string> F;
	vector<int> V;
	int cost[51][51];
	
	int bfs(int id) {
		int i,dist[51][51],x,y;
		
		FOR(y,R) FOR(x,C) dist[y][x]=10000000;
		dist[V[id]/100][V[id]%100]=0;
		queue<int> Q;
		Q.push(V[id]);
		
		while(!Q.empty()) {
			int cy=Q.front()/100,cx=Q.front()%100;
			Q.pop();
			FOR(i,4) {
				int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
				int tx=cx+dx[i],ty=cy+dy[i];
				if(tx<0 || tx>=C || ty<0 || ty>=R || F[ty][tx]=='#') continue;
				if(dist[ty][tx]>dist[cy][cx]+1) {
					dist[ty][tx]=dist[cy][cx]+1;
					Q.push(ty*100+tx);
				}
			}
		}
		
		FOR(x,V.size()) cost[id][x]=dist[V[x]/100][V[x]%100];
	}
	
	int exterminate(vector <string> field) {
		F=field;
		R=field.size();
		C=field[0].size();
		int y,x,z;
		
		V.clear();
		FOR(y,R) FOR(x,C) if(field[y][x]=='$') V.push_back(y*100+x);
		FOR(y,R) FOR(x,C) if(field[y][x]>='1' && field[y][x]<='9') V.push_back(y*100+x);
		if(V.size()>10) return -1;
		
		FOR(x,V.size()) bfs(x);
		int mi=10000000,i;
		vector<int> CC;
		for(x=1;x<V.size();x++) CC.push_back(x);
		z=CC.size();
		do {
			int tc[11],c=0;
			tc[0]=0;
			FOR(x,z) tc[x+1]=tc[x]+cost[c][CC[x]], c=CC[x];
			if(tc[z]<mi) {
				int ng=0;
				FOR(x,z) {
					if(tc[z]-tc[x+1]>=F[V[CC[x]]/100][V[CC[x]]%100]-'0') ng++;
				}
				if(ng==0) mi=tc[z];
			}
			
		} while(next_permutation(CC.begin(),CC.end()));
		
		if(mi<10000000) return mi;
		return -1;
	}
};

まとめ

10の階乗位なら時間は余裕だね。