ARC019 C.最後の森

問題リンク

• 分岐点全探索で良かったらしい。
  • 村、城、ほこらの各地点からBFSする
  • 経路は 村→分岐点→ほこら→分岐点→城 として表せる
  • 各点Pについて、村→Pのコスト + 2*(ほこら→Pのコスト) + 城→Pのコスト を調べる
    • 倒すモンスターの数をk以下にした時のコストを持っておけばO(k^2)で分かる
  • 全体でO(n^2 k^2)
• 本番で通らなかったのは、普通にバグってたのと分岐点に敵がいた場合の処理漏れ。

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

int step[3][101][50][50];

class Node {
public:
    int k, x, y;
    Node(int k, int x, int y) : k(k), x(x), y(y) {}
};

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

int solve(const vector<string>& vs, int K){
    int n = vs.size(), m = vs[0].size();
    memset(step, -1, sizeof(step));
    for(int start=0;start<3;start++){
        queue<Node> qu;
        int sx, sy;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(vs[i][j] == "SCG"[start]) sx = i, sy = j;
        step[start][0][sx][sy] = 0;
        qu.push(Node(0, sx, sy));
        while(!qu.empty()){
            Node nd = qu.front(); qu.pop();
            for(int i=0;i<4;i++){
                int nx = nd.x+dx[i];
                int ny = nd.y+dy[i];
                if(nx < 0 || n <= nx || ny < 0 || m <= ny) continue;
                int nk = nd.k + (vs[nx][ny]=='E');
                if(vs[nx][ny] == 'T') continue;
                if(nk > K) continue;
                if(step[start][nk][nx][ny] != -1) continue;
                
                step[start][nk][nx][ny] = step[start][nd.k][nd.x][nd.y]+1;
                qu.push(Node(nk, nx, ny));
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                int best = -1;
                for(int k=0;k<=K;k++){
                    if(best == -1 || (step[start][k][i][j] != -1 && best > step[start][k][i][j])){
                        best = step[start][k][i][j];
                    }
                    step[start][k][i][j] = best;
                }
            }
        }
    }

    int res = -1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int upperB = K+(vs[i][j] == 'E');
            int upperC = K+2*(vs[i][j] == 'E');
            for(int kA=0;kA<=K;kA++){
                if(step[0][kA][i][j] == -1) continue;
                for(int kB=0;kB<=K;kB++){
                    if(kA+kB > upperB) break;
                    if(step[1][kB][i][j] == -1) continue;
                    int kC = min(K, upperC-(kA+kB));
                    if(step[2][kC][i][j] == -1) continue;
                    int sum = step[0][kA][i][j] + 2*step[1][kB][i][j] + step[2][kC][i][j];
                    if(res == -1 || res > sum) res = sum;
                }
            }
        }
    }
    return res;
}

int main(){
    int N, M, K;
    while(cin >> N >> M >> K){
        vector<string> vs(N);
        for(int i=0;i<N;i++) cin >> vs[i];
        cout << solve(vs, K) << endl;
    }
}