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; }