No.34 砂漠の行商人

No.34 砂漠の行商人 - yukicoder

• 計算量が O(N^2*V) とかになるのでどうしたもんかなーと悩んだ問題。
• 砂漠のレベルが 9 までしかないので実質計算量が落ちるという問題だった。ココらへんの計算量見積もりが甘い...。あと問題の性質への気付き力がたりない。
• 到達コストが小さいなら更新する。って部分。最初更新してしまうとコストは大きくても移動時間が短いケースが除かれるんじゃね？って思った。よく考えるとダイクストラじゃなくて単なる幅優先探索なので問題なかった。

class DesertChapman {
public:
    void solve(void) {
            int N,V,sx,sy,gx,gy;
            cin>>N>>V>>sx>>sy>>gx>>gy;
            --sx,--sy,--gx,--gy;
            vector<vector<int>> fld(N,vector<int>(N,0));
            REP(i,N)
            REP(j,N)
                cin>>fld[i][j];

            const int inf = (1<<30);

            // cost[y][x] := (x,y) までの到達コストの最小値
            vector<vector<int>> cost(N,vector<int>(N,inf));
            queue<tuple<int,int,int,int>> que;
            // 幅優先探索でやる
            que.emplace(sx,sy,0,0);
            // 最悪ゴールまで辿りつけないケースは全探索になるので
            // O(N^2*V) <= 10^10 となる。
            //
            // ただし障害物がないので
            // ((横の移動最大回数)+(縦の移動最大回数))*max(fld[y][x]) < V なら到達可能なので
            // O(N^2*V) <= 1.8*10^7 程度の計算量になる。
            //
            while (!que.empty())
            {
                int x,y,c,t;
                tie(x,y,c,t) = que.front();
                que.pop();

                const int dx[] = {1,0,-1,0};
                const int dy[] = {0,-1,0,1};
                REP(d,4)
                {
                    int nx = x+dx[d];
                    int ny = y+dy[d];

                    if (nx < 0 || ny < 0 || N <= nx || N <= ny)
                        continue;

                    int nc = c+fld[ny][nx];
                    // 体力が付きてしまった
                    if (nc >= V)
                        continue;

                    // 到達できたら終了。幅優先なのでこれが最短時間
                    if (nx==gx && ny==gy)
                    {
                        cout<<t+1<<endl;
                        return;
                    }
                    // 到達コストを更新できるなら更新して enqueue
                    // 更新前の到達コストの方が到達時間が短い可能性があるが、
                    // その場合はとなりのマスへの移動がすでに enqueu されているはず。
                    if (cost[ny][nx] > nc)
                    {
                        cost[ny][nx] = c+fld[ny][nx];
                        que.emplace(nx,ny,cost[ny][nx],t+1);
                    }
                }
            }
            cout<<-1<<endl;
            return;
    }
};