AtCoder Regular Contest #003 C : 暗闇帰り道

問題概要

W*H(W,H<500)のボードがあり、各マスには数値が定められていて、数値は時間とともに減少する。このとき、スタート地点からゴールまでのボトルネックを最大化する問題。

解法

答について二分探索する。こうすると、各マスにある時刻で入れるかどうかが簡単に判定できる。なお、答は十分小さい値をとりうるので、low=0.0なら到達不能、とすると間違える。

acceptされたコード

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;

const int MAX_W = 500;
const int INF = 1<<29;

typedef pair<int,int> pos;

int H, W;
int sx, sy;
char board[MAX_W][MAX_W + 1];
int dist[MAX_W][MAX_W];

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

bool check(double lim){
	queue< pos > que;
	que.push(pos(sy, sx));
	for(int i=0; i<H; ++i){
		fill(dist[i], dist[i]+W, INF);
	}
	dist[sy][sx] = 1;

	for(;!que.empty();){
		pos tp = que.front(); que.pop();
		int y = tp.first, x = tp.second;
		int t = dist[y][x];
		for(int k=0; k<4; ++k){
			int ny = y + dy[k], nx = x + dx[k];
			if( !(0<=ny && ny<H && 0<=nx && nx<W) ){
				continue;
			}
			if(dist[ny][nx] == INF){
				if(board[ny][nx] == 'g'){
					return true;
				}
				if(isdigit(board[ny][nx]) && lim < (board[ny][nx]&15) * pow(0.99, t)){
					dist[ny][nx] = t + 1;
					que.push(pos(ny, nx));
				}
			}
		}
	}

	return false;
}

void init(){
	scanf("%d%d ", &H, &W);
	for(int i=0; i<H; ++i){
		scanf(" %s ", board[i]);
	}
	for(int i=0; i<H; ++i){
		for(int j=0; j<W; ++j){
			if(board[i][j] == 's'){
				sy = i;
				sx = j;
			}
		}
	}
}

double solve(){
	double low = 0.0, high = 10.0;
	if(!check(-1)){
		return -1;
	}
	for(int _=0; _<50; ++_){
		double mid = (low + high) / 2.0;
		if(check(mid)){
			low = mid;
		}
		else{
			high = mid;
		}
	}
	return low;
}

int main(){
	init();
	printf("%.13f\n", solve());

	return 0;
}