ARC 003 C - 暗闇帰り道
問題概要
省略。
解法
sからgまでの経路が存在するとき、答えを小さくすれば、条件を満たし、答えを大きくしていくと、条件を満たさなくなる。そのため、答えを2分探索していけばよいことになる。また、ある地点まで、最短でいったときが、そのますの明るさを最大とするので、bfsで最短経路をたどりながら、決めた値を満たしながら、sからgへ行けるかを確かめればいい。
ミス
すぐに2分探索だと気付きたい。 hantei()のbfsで調べたところを記録して何回も調べないようにするの忘れてて、TLEしまくって^^
コード
#include <iostream> #include <string> #include <queue> #include <cmath> #include <cstdio> using namespace std; #define rep(i,n) for(int i=0;i<(n);i++) int dy[] = {1, 0, 0, -1}; int dx[] = {0, 1, -1, 0}; const int INF = 1e9; int h, w, sy, sx, gy, gx; string c[510]; bool used_[510][510]; bool hantei(void){//s->gの判定 rep(i, 510)rep(j, 510) used_[i][j] = false; queue<pair<int ,int> > q; q.push(make_pair(sy, sx)); while(!q.empty()){ auto now = q.front(); q.pop(); rep(i, 4){ int ny = now.first + dy[i], nx = now.second + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(ny == gy && nx == gx){ return true; } if(used_[ny][nx]) continue; if(c[ny][nx] == '#') continue; q.push(make_pair(ny, nx)); used_[ny][nx] = true; } } return false; } int used[510][510];//最短何回目にたどり着けるか bool bfs(double lim){ rep(i, 510)rep(j, 510)used[i][j] = INF; queue<pair<int, int> > q; q.push(make_pair(sy, sx)); used[sy][sx] = 1; while(!q.empty()){ auto now = q.front(); q.pop(); int t = used[now.first][now.second]; rep(i, 4){ int ny = now.first + dy[i], nx = now.second + dx[i]; if(!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if(c[ny][nx] == '#') continue; if(used[ny][nx] != INF) continue; if(ny == gy && nx == gx) return true; //limより明るさ上か if(lim < (double)(c[ny][nx] - '0') * pow(0.99, t)){ q.push(make_pair(ny, nx)); used[ny][nx] = t + 1; } } } return false; } int main(void){ cin >> h >> w; rep(i, h) cin >> c[i]; rep(i, h)rep(j, w){ if(c[i][j] == 's'){ sy = i; sx = j; } if(c[i][j] == 'g'){ gy = i; gx = j; } } if(!hantei()){ printf("-1\n"); return 0; } //2分探索 double r = 10.0, l = 0.0; while(r - l > 1e-9){ double mid = (l + r) / 2.0; // printf("mid %f\n", mid); if(bfs(mid)){//もっと大きくできる l = mid; }else{ r = mid; } } printf("%.9f\n", l); return 0; }