GCJ2012 Round1B B. Tide Goes In, Tide Goes Out

2012-05-06

14:37 |

カヤックが W x H セルの洞窟にいて水が毎秒10cmで下がる。水位と各セルの地面と天井の高さによって隣のセルに進めるかどうか決まる（詳細省略...）ゴールまで行く最短時間を求める問題。

右か下にしか進まないと思ってて、O(WH) の DP を書いた
水位が下がらなくても進める時間はカウントしない処理を入れる
Small の実行結果を見ると INF になってるのがあっておかしい
そうか左に進むこともあるのか
BFS
WA
おわり

（あとで）

なるほど Dijkstra か..
deque を priority_queue に書き換える
priority_queue は大きいのから出てくるので時間を負にして push
AC
各セルの水位も保存してるけど、水位は時刻から決まるから不要だった。いろいろ無駄に複雑に書いてしまった

#define INF 100000000

int main() {
	int test_cases;
	cin>>test_cases;
	REP(ttt, test_cases) {
		int L, H, W;
		cin>>L>>H>>W;
		VVI ce(H, VI(W));
		VVI fl(H, VI(W));
		REP(y, H) REP(x, W) cin>>ce[y][x];
		REP(y, H) REP(x, W) cin>>fl[y][x];
		VVI ti(H, VI(W, INF));
		VVI he(H, VI(W));
		VVI st(H, VI(W, 1));
		st[0][0] = 0;
		ti[0][0] = 0;
		he[0][0] = L;
		VVI vis(H, VI(W));
		priority_queue <pair <int, pair <int, int> > > q;
		//deque<PII> q;
		q.push(MP(0, MP(0,0))); // x, y
		int ok=0;
		while(q.size()) {
			int x = q.top().second.first;
			int y = q.top().second.second;
			//cout<<"pop "<<q.top().first<<"  "<<x<<" "<<y<<endl;
			q.pop();
			if(ti[y][x]==INF) continue;
			if(x==W-1 && y==H-1) {ok=1;break;}
			if(vis[y][x]) continue;
			vis[y][x]=1;
			int tdx[] = {1, 0, -1, 0};
			int tdy[] = {0, 1, 0, -1};
			REP(dir, 4) {
				if(dir==0 && x>=W-1) continue; // right
				if(dir==1 && y>=H-1) continue; // down
				if(dir==2 && 0>=x) continue; // left
				if(dir==3 && 0>=y) continue; // top
				int nx = x+tdx[dir];
				int ny = y+tdy[dir];
				int lvl = he[y][x];
				if(fl[y][x]+50<=ce[ny][nx] && fl[ny][nx]+50<=ce[ny][nx] && fl[ny][nx]+50<=ce[y][x] ) {
					int wait = max(0, lvl-(ce[ny][nx]-50));
					if(!st[y][x] && wait==0) {
						st[ny][nx] = 0;
						ti[ny][nx] = ti[y][x];
						he[ny][nx] = he[y][x];
					} else
					if(fl[y][x]+20<=lvl-wait) {
						if(ti[y][x]+wait+10 < ti[ny][nx]) {
							ti[ny][nx] = ti[y][x]+wait+10;
							he[ny][nx] = lvl-(wait+10);
						}
					} else {
						if(ti[y][x]+wait+100 < ti[ny][nx]) {
							ti[ny][nx] = ti[y][x]+wait+100;
							he[ny][nx] = lvl-(wait+100);
						}
					}
					//cout<<"push "<<ti[ny][nx]<<" "<<nx<<" "<<ny<<endl;
					q.push(MP(-ti[ny][nx], MP(nx, ny)));
				}
			}
			//cout<<"loop end"<<endl;
		}
		//cout<<ti<<endl;
		//cout<<he<<endl;
		//cout<<st<<endl;
		//if(!ok) cout<<"!!!!"<<endl;
		cout<<"Case #"<<ttt+1<<": "<<(double)ti[H-1][W-1]/10<<endl;
	}
	return 0;
}