提出 #18338763 - AtCoder Beginner Contest 184

コンテスト時間: 2020-11-22 21:00:00+0900 ~ 2020-11-22 22:40:00+0900 (100分) AtCoderホームへ戻る

提出 #18338763

ソースコード拡げる

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <sstream>
#include <unordered_map>
#include <climits>
#include <unordered_set>
#include <utility>
#include <queue>
#include <cmath>
#include <map>
#include <iomanip>

using namespace std;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

struct Node {
    int depth=0;
    vector<int> coord={0,0};
};

int main() {
    int h, w;
    cin >> h >> w;

    vector<vector<char>> grid(h);
    unordered_map<char, vector<vector<int>>> neighbors;
    for(int i='a'; i <= 'z'; ++i){
        neighbors[(char)i] = {};
    }
    
    vector<int> g_coord;
    vector<int> s_coord;
    for(int i=0; i < h; ++i){
        vector<char> temp(w);
        grid.at(i) = temp;
        for(int j=0; j < w; ++j){
            cin >> grid.at(i).at(j);
            if(grid.at(i).at(j) == 'S'){
                s_coord = {i, j};
            }
            if(grid.at(i).at(j) == 'G'){
                g_coord = {i, j};
            }
            if(grid.at(i).at(j) >= 'a' && grid.at(i).at(j) <= 'z'){
                neighbors[grid.at(i).at(j)].push_back({i,j});
            }
        }
    }
    

    queue<Node*> q;
    Node* start = new Node;
    start->coord = s_coord;
    q.push(start);
    unordered_set<pair<int, int>, pair_hash> searched;
    searched.insert(make_pair(s_coord.at(0), s_coord.at(1)));
    while(!q.empty()){
        auto current = q.front();
        q.pop();
        if(grid.at(current->coord.at(0)).at(current->coord.at(1)) == 'G'){
            cout << current->depth << "\n";
            return 0;
        }
        if(grid.at(current->coord.at(0)).at(current->coord.at(1)) != '#'){
            if(grid.at(current->coord.at(0)).at(current->coord.at(1)) <= 'z' && grid.at(current->coord.at(0)).at(current->coord.at(1)) >= 'a'){
                //teleport
                for(int i=0; i < neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].size(); ++i){
                    if(searched.find(make_pair(neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(0), neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(1))) == searched.end()){
                        searched.insert(make_pair(neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(0), neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(1)));
                        Node* newNode = new Node;
                        newNode->depth = current->depth+1;
                        newNode->coord = {neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(0), neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))].at(i).at(1)};
                        q.push(newNode);
                    }
                }
                neighbors[grid.at(current->coord.at(0)).at(current->coord.at(1))] = {};
            }
            if(current->coord.at(0) + 1 < h && searched.find(make_pair(current->coord.at(0)+1, current->coord.at(1))) == searched.end()){
                searched.insert(make_pair(current->coord.at(0)+1, current->coord.at(1)));
                Node* newNode = new Node;
                newNode->depth = current->depth+1;
                newNode->coord = {current->coord.at(0)+1, current->coord.at(1)};
                q.push(newNode);
            }
            if(current->coord.at(0) - 1 >= 0 && searched.find(make_pair(current->coord.at(0)-1, current->coord.at(1))) == searched.end()){
                searched.insert(make_pair(current->coord.at(0)-1, current->coord.at(1)));
                Node* newNode = new Node;
                newNode->depth = current->depth+1;
                newNode->coord = {current->coord.at(0)-1, current->coord.at(1)};
                q.push(newNode);
            }
            if(current->coord.at(1) + 1 < w && searched.find(make_pair(current->coord.at(0), current->coord.at(1)+1)) == searched.end()){
                searched.insert(make_pair(current->coord.at(0), current->coord.at(1)+1));
                Node* newNode = new Node;
                newNode->depth = current->depth+1;
                newNode->coord = {current->coord.at(0), current->coord.at(1)+1};
                q.push(newNode);
            }
            if(current->coord.at(1) -1 >= 0 && searched.find(make_pair(current->coord.at(0), current->coord.at(1)-1)) == searched.end()){
                searched.insert(make_pair(current->coord.at(0), current->coord.at(1)-1));
                Node* newNode = new Node;
                newNode->depth = current->depth+1;
                newNode->coord = {current->coord.at(0), current->coord.at(1)-1};
                q.push(newNode);
            }
        }
        
    }

    cout << "-1\n";
    return 0;
}

提出情報

提出日時	2020-11-22 22:25:25+0900
問題	E - Third Avenue
ユーザ	jcarlson212
言語	C++ (Clang 10.0.0)
得点	0
コード長	4961 Byte
結果	TLE
実行時間	3321 ms
メモリ	487028 KiB

ジャッジ結果

セット名

Sample

All

得点 / 配点

0 / 0

0 / 500

結果

× 3

AC	× 34
TLE	× 4

セット名	テストケース
Sample	sample_01.txt, sample_02.txt, sample_03.txt
All	hand_01.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, random_33.txt, random_34.txt, sample_01.txt, sample_02.txt, sample_03.txt

ケース名	結果	実行時間	メモリ
hand_01.txt	AC	11 ms	3092 KiB
random_01.txt	AC	2 ms	3200 KiB
random_02.txt	AC	2 ms	3236 KiB
random_03.txt	AC	2 ms	3116 KiB
random_04.txt	AC	2 ms	3236 KiB
random_05.txt	AC	2 ms	3164 KiB
random_06.txt	AC	2 ms	3196 KiB
random_07.txt	AC	2 ms	3108 KiB
random_08.txt	AC	2 ms	3200 KiB
random_09.txt	AC	2 ms	3188 KiB
random_10.txt	AC	4 ms	3112 KiB
random_11.txt	AC	2 ms	3196 KiB
random_12.txt	AC	2 ms	3212 KiB
random_13.txt	AC	3 ms	3224 KiB
random_14.txt	AC	2 ms	3116 KiB
random_15.txt	AC	2 ms	3132 KiB
random_16.txt	AC	53 ms	9348 KiB
random_17.txt	AC	2266 ms	138720 KiB
random_18.txt	AC	417 ms	43456 KiB
random_19.txt	AC	37 ms	6020 KiB
random_20.txt	AC	530 ms	53868 KiB
random_21.txt	AC	28 ms	6552 KiB
random_22.txt	AC	34 ms	8532 KiB
random_23.txt	AC	615 ms	67568 KiB
random_24.txt	AC	889 ms	70872 KiB
random_25.txt	AC	164 ms	34624 KiB
random_26.txt	AC	8 ms	3684 KiB
random_27.txt	AC	296 ms	37188 KiB
random_28.txt	AC	17 ms	5604 KiB
random_29.txt	AC	8 ms	3476 KiB
random_30.txt	AC	369 ms	51220 KiB
random_31.txt	TLE	3314 ms	232960 KiB
random_32.txt	TLE	3314 ms	225144 KiB
random_33.txt	TLE	3314 ms	225228 KiB
random_34.txt	TLE	3321 ms	487028 KiB
sample_01.txt	AC	10 ms	3096 KiB
sample_02.txt	AC	2 ms	3172 KiB
sample_03.txt	AC	2 ms	3088 KiB