Submission #144735


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
using namespace std;

typedef pair<int, int> P;
const int MAX_R = 52;
const int MAX_C = 52;
const int MAX_K = 100;
set< set<P> > arrived[MAX_R][MAX_C];
int R, C, K;
char forest[MAX_R][MAX_C];
const int dr[] = {-1,0,1,0};
const int dc[] = {0,1,0,-1};

bool check(int r, int c) {
    return (r >= 0 && r < R && c >= 0 && c < C);
}

int main(int argc, const char * argv[])
{
    scanf("%d %d %d", &R, &C, &K);
    int s_r = 0, s_c = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            char c;
            scanf(" %c", &c);
            forest[i][j] = c;
            if (c == 'S') {
                s_r = i;
                s_c = j;
            }
        }
    }
    set<P> ene;
    
    queue<P> posi;
    queue<bool> sord;
    queue<set<P>> knocked;
    queue<int> count;
    posi.push(P(s_r, s_c));
    sord.push(false);
    knocked.push(ene);  //空
    count.push(0);
    arrived[s_r][s_c].insert(ene);
    int ret = -1;
    while (!posi.empty()) {
        P p = posi.front(); posi.pop();
        bool have_sord = sord.front(); sord.pop();
        set<P> k_e = knocked.front(); knocked.pop();
        int t = count.front(); count.pop();
        if (!have_sord && forest[p.first][p.second] == 'C') {
            have_sord = true;
        }
        if (have_sord && forest[p.first][p.second] == 'G') {
            ret = t;
            break;
        }
        if (forest[p.first][p.second] == 'E') {
            if (k_e.find(P(p.first, p.second)) == k_e.end()) {
                k_e.insert(P(p.first, p.second));
            }
        }
        for (int i = 0; i < 4; i++) {
            int nxt_r = p.first + dr[i];
            int nxt_c = p.second + dc[i];
            if (check(nxt_r, nxt_c)) {  //範囲内
                if (forest[nxt_r][nxt_c] == 'T') continue;
                else if (forest[nxt_r][nxt_c] == '.' ||
                         forest[nxt_r][nxt_c] == 'S' ||
                         forest[nxt_r][nxt_c] == 'G') {
                    
                    if (arrived[nxt_r][nxt_c].find(k_e) == arrived[nxt_r][nxt_c].end()) {  //移動可
                        arrived[nxt_r][nxt_c].insert(k_e);
                        posi.push(P(nxt_r, nxt_c));
                        sord.push(have_sord);
                        knocked.push(k_e);
                        count.push(t+1);
                        
                    }
                } else if (forest[nxt_r][nxt_c] == 'C') {
                    if (arrived[nxt_r][nxt_c].find(k_e) == arrived[nxt_r][nxt_c].end()) {  //移動可
                        arrived[nxt_r][nxt_c].insert(k_e);
                        k_e.insert(P(nxt_r, nxt_c));
                        posi.push(P(nxt_r, nxt_c));
                        sord.push(have_sord);
                        knocked.push(k_e);
                        count.push(t+1);
                        
                    }
                } else if (forest[nxt_r][nxt_c] == 'E') {
                    if (k_e.find(P(nxt_r, nxt_c)) == k_e.end()) {  //初めて戦う
                        if (k_e.size() < K + (have_sord)? 1 : 0) {  //まだ戦える
                            arrived[nxt_r][nxt_c].insert(k_e);
                            posi.push(P(nxt_r, nxt_c));
                            sord.push(have_sord);
                            knocked.push(k_e);
                            count.push(t+1);
                        }
                    } else {  //すでに倒している
                        if (arrived[nxt_r][nxt_c].find(k_e) == arrived[nxt_r][nxt_c].end()) {
                            arrived[nxt_r][nxt_c].insert(k_e);
                            posi.push(P(nxt_r, nxt_c));
                            sord.push(have_sord);
                            knocked.push(k_e);
                            count.push(t+1);
                        }
                    }
                }
            }
        }
    }
    printf("%d\n", ret);
    return 0;
}

Submission Info

Submission Time
Task C - 最後の森
User koyahi
Language C++ (G++ 4.6.4)
Score 0
Code Size 4151 Byte
Status

Compile Error

./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:41:19: error: ‘knocked’ was not declared in this scope
./Main.cpp:41:16: error: ‘>>’ should be ‘> >’ within a nested template argument list
./Main.cpp:24:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:29:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]