ARC003 C - 暗闇帰り道

C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder

• 二分探索 + bfs な問題。
• 以前解いたのにもかかわらず間違えまくった...。
• bfs では pop 直後に vis を見てはじいてしまったり(致命的)、high = 1<<30 から始めたり、val = min(val,pow(0.99,t)*..) を保持しておこうとしたり...無駄なことを。シンプルに書くことを心がけよう。

class C_DarknessWayHome {
public:
    void solve(void) {
        int N,M;
        cin>>N>>M;
        vector<string> field(N);

        int sx,sy,gx,gy;
        REP(i,N)
        {
            cin>>field[i];
            REP(j,M)
            {
                if (field[i][j] == 'g')
                { gx = j; gy = i; }
                if (field[i][j] == 's')
                { sx = j; sy = i; }
            }
        }


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

        // low より明るい状態で goal までたどりつけるか bfs
        auto bfs = [&](double low) {
            queue<tuple<int,int,int>> que;
            que.emplace(sx,sy,0);

            vector<vector<bool>> vis(N,vector<bool>(M,false));
            while ( !que.empty() )
            {
                int x,y,t;
                tie(x,y,t) = que.front();
                que.pop();

                REP(d,4)
                {
                    int nx = x+dx[d];
                    int ny = y+dy[d];

                    if (nx < 0 || M <= nx || ny < 0 || N <= ny)
                        continue;
                    if (field[ny][nx] == '#')
                        continue;
                    if (field[ny][nx] == 's')
                        continue;
                    if (field[ny][nx] == 'g')
                        return true;
                    if ( vis[ny][nx] )
                        continue;

                    double val = pow(0.99,t+1)*(field[ny][nx]-'0');
                    if (val < low)
                        continue;
                    vis[ny][nx] = true;
                    que.emplace(nx,ny,t+1);
                }
            }
            return false;
        };

        // ゴールに到達しないケースを先にやる
        if ( !bfs(0.0) )
        {
            cout<<-1<<endl;
            return;
        }
        double low  = 0;
        double high = 10;

        // fabs(low-high) < EPS の EPS が小さすぎるとループ回数が
        // 大きくなって TLE してしまうので最大 100 回でやる
        //
        // O(100*N*M)
        REP(i,100)
        {
            if (fabs(low-high) < 1e-10)
                break;
            double mid = (low+high)*0.5;
            if ( bfs(mid) )
                low = mid;
            else
                high = mid;
        }
        cout<<setprecision(20)<<low<<endl;
    }
};