TopCoder SRM 583 Div2 Hard GameOnABoard

拍子抜けした問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12556

問題

0と1がグリッド状に敷き詰められたボードを用いてゲームを行う。
先手は、いずれかのセルを選択し、後手は別のセルを選択する。
このとき、かかるコストは先手のセルから後手のセルまで隣接マスを辿って移動するときに経由するセルの数値の和である。

先手はコストを最少化、後手はコストを最大化しようとする場合、先手が取れる最少コストを答えよ。

解法

先手が取る各セルに対し、そこから他の全セルに至るコストをDijkstraで求めるだけ。

この問題は最大でセルが1600あるのでFloydは無理。
グリッドの中心のセルを取ってもコストの最大値は高々40程度なので、1600回も全セルを探索するFloydは無駄になる。

class GameOnABoard {
	public:
	int H,W;
	int cc[40][40];
	int dodo(int X,int Y,int cm) {
		int i,j,k,x,y,ma;
		int dist[40][40];
		
		FOR(y,H) FOR(x,W) dist[y][x]=999;
		ma=dist[Y][X]=cc[Y][X];
		
		set<int> Q;
		Q.insert(dist[Y][X]*10000+Y*100+X);
		while(!Q.empty()) {
			int k=*Q.begin();
			Q.erase(k);
			int cx=k%100,cy=(k/100)%100;
			
			int dx[4]={0,0,1,-1};
			int dy[4]={1,-1,0,0};
			FOR(i,4) {
				int tx=cx+dx[i],ty=cy+dy[i];
				if(tx<0||tx>=W||ty<0||ty>=H) continue;
				
				if(dist[ty][tx]>dist[cy][cx]+cc[ty][tx]) {
					dist[ty][tx]=dist[cy][cx]+cc[ty][tx];
					ma=max(ma,dist[ty][tx]);
					if(ma>=cm) return ma;
					Q.insert(dist[ty][tx]*10000+ty*100+tx);
				}
			}
		}
		return ma;
	}
	
	int optimalChoice(vector <string> cost) {
		int x,y;
		H=cost.size();
		W=cost[0].size();
		
		int mi=41;
		FOR(y,H) FOR(x,W) cc[y][x]=cost[y][x]-'0';
		FOR(y,H) FOR(x,W) mi=min(mi,dodo(x,y,mi));
		
		return mi;
	}
}

まとめ

最初「Floydは当然無理だし、全セルでDijkstraしても難しいかな…」と思ったらあっさり通ってしまった。
もっとグリッドであることとコストが0と1しかないことを使うのかと思ったら意外。