Submission #144737


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 4153 Byte
Status
Exec Time 2068 ms
Memory 280160 KB

Compile Error

./Main.cpp: In function ‘int main(int, const char**)’:
./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]

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
× 9
× 4
× 17
Set Name Test Cases
All case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt
Case Name Status Exec Time Memory
case_01.txt 20 ms 924 KB
case_02.txt 23 ms 1048 KB
case_03.txt 23 ms 968 KB
case_04.txt 23 ms 920 KB
case_05.txt 20 ms 936 KB
case_06.txt 24 ms 1048 KB
case_07.txt 2045 ms 132512 KB
case_08.txt 106 ms 9256 KB
case_09.txt 2055 ms 192300 KB
case_10.txt 2058 ms 177960 KB
case_11.txt 2057 ms 199988 KB
case_12.txt 20 ms 1048 KB
case_13.txt 2057 ms 215732 KB
case_14.txt 2054 ms 178984 KB
case_15.txt 22 ms 1040 KB
case_16.txt 2058 ms 205100 KB
case_17.txt 2065 ms 280160 KB
case_18.txt 23 ms 1300 KB
case_19.txt 2068 ms 248908 KB
case_20.txt 24 ms 1560 KB
case_21.txt 2059 ms 240444 KB
case_22.txt 2052 ms 151760 KB
case_23.txt 2056 ms 194356 KB
case_24.txt 2050 ms 179356 KB
case_25.txt 2056 ms 218152 KB
case_26.txt 2042 ms 113956 KB
case_27.txt 226 ms 18216 KB
case_28.txt 2053 ms 151460 KB
case_29.txt 22 ms 1044 KB
case_30.txt 2046 ms 143652 KB
sample_01.txt 22 ms 1040 KB
sample_02.txt 22 ms 1044 KB
sample_03.txt 23 ms 1052 KB
sample_04.txt 29 ms 1360 KB