#859981 (C++17) No.5015 Escape from Labyrinth

提出ソース

結果

問題	No.5015 Escape from Labyrinth
ユーザー	first_vil
提出日時	2023-04-15 13:52:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3 ms / 3,000 ms
コード長	6,158 bytes
コンパイル時間	2,392 ms
コンパイル使用メモリ	214,928 KB
実行使用メモリ	4,376 KB
スコア	12,310
最終ジャッジ日時	2023-04-15 13:52:54
合計ジャッジ時間	7,623 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	3 ms 4,372 KB
testcase_01	AC	2 ms 4,372 KB
testcase_02	AC	2 ms 4,372 KB
testcase_03	AC	2 ms 4,368 KB
testcase_04	AC	3 ms 4,372 KB
testcase_05	AC	2 ms 4,368 KB
testcase_06	AC	2 ms 4,368 KB
testcase_07	AC	3 ms 4,368 KB
testcase_08	AC	2 ms 4,376 KB
testcase_09	AC	2 ms 4,368 KB
testcase_10	AC	2 ms 4,372 KB
testcase_11	AC	3 ms 4,368 KB
testcase_12	AC	2 ms 4,368 KB
testcase_13	AC	3 ms 4,372 KB
testcase_14	AC	3 ms 4,368 KB
testcase_15	AC	2 ms 4,372 KB
testcase_16	AC	2 ms 4,368 KB
testcase_17	AC	2 ms 4,372 KB
testcase_18	AC	2 ms 4,372 KB
testcase_19	AC	2 ms 4,372 KB
testcase_20	AC	2 ms 4,372 KB
testcase_21	AC	2 ms 4,372 KB
testcase_22	AC	3 ms 4,372 KB
testcase_23	AC	2 ms 4,368 KB
testcase_24	AC	3 ms 4,372 KB
testcase_25	AC	2 ms 4,368 KB
testcase_26	AC	2 ms 4,368 KB
testcase_27	AC	2 ms 4,372 KB
testcase_28	AC	3 ms 4,368 KB
testcase_29	AC	2 ms 4,368 KB
testcase_30	AC	2 ms 4,372 KB
testcase_31	AC	2 ms 4,372 KB
testcase_32	AC	2 ms 4,368 KB
testcase_33	AC	2 ms 4,372 KB
testcase_34	AC	2 ms 4,372 KB
testcase_35	AC	2 ms 4,372 KB
testcase_36	AC	2 ms 4,368 KB
testcase_37	AC	2 ms 4,372 KB
testcase_38	AC	2 ms 4,368 KB
testcase_39	AC	2 ms 4,372 KB
testcase_40	AC	2 ms 4,372 KB
testcase_41	AC	2 ms 4,368 KB
testcase_42	AC	2 ms 4,368 KB
testcase_43	AC	2 ms 4,372 KB
testcase_44	AC	2 ms 4,372 KB
testcase_45	AC	2 ms 4,372 KB
testcase_46	AC	2 ms 4,368 KB
testcase_47	AC	2 ms 4,372 KB
testcase_48	AC	2 ms 4,368 KB
testcase_49	AC	2 ms 4,368 KB
testcase_50	AC	2 ms 4,368 KB
testcase_51	AC	2 ms 4,372 KB
testcase_52	AC	2 ms 4,372 KB
testcase_53	AC	2 ms 4,368 KB
testcase_54	AC	2 ms 4,368 KB
testcase_55	AC	2 ms 4,368 KB
testcase_56	AC	2 ms 4,368 KB
testcase_57	AC	2 ms 4,368 KB
testcase_58	AC	2 ms 4,368 KB
testcase_59	AC	2 ms 4,372 KB
testcase_60	AC	2 ms 4,372 KB
testcase_61	AC	3 ms 4,368 KB
testcase_62	AC	2 ms 4,372 KB
testcase_63	AC	2 ms 4,368 KB
testcase_64	AC	3 ms 4,372 KB
testcase_65	AC	3 ms 4,368 KB
testcase_66	AC	2 ms 4,372 KB
testcase_67	AC	2 ms 4,368 KB
testcase_68	AC	2 ms 4,372 KB
testcase_69	AC	2 ms 4,372 KB
testcase_70	AC	2 ms 4,372 KB
testcase_71	AC	2 ms 4,368 KB
testcase_72	AC	2 ms 4,372 KB
testcase_73	AC	2 ms 4,368 KB
testcase_74	AC	2 ms 4,372 KB
testcase_75	AC	2 ms 4,368 KB
testcase_76	AC	2 ms 4,372 KB
testcase_77	AC	2 ms 4,372 KB
testcase_78	AC	2 ms 4,372 KB
testcase_79	AC	2 ms 4,368 KB
testcase_80	AC	2 ms 4,372 KB
testcase_81	AC	2 ms 4,368 KB
testcase_82	AC	2 ms 4,368 KB
testcase_83	AC	2 ms 4,368 KB
testcase_84	AC	3 ms 4,368 KB
testcase_85	AC	2 ms 4,368 KB
testcase_86	AC	2 ms 4,372 KB
testcase_87	AC	3 ms 4,372 KB
testcase_88	AC	2 ms 4,368 KB
testcase_89	AC	2 ms 4,368 KB
testcase_90	AC	2 ms 4,368 KB
testcase_91	AC	2 ms 4,372 KB
testcase_92	AC	2 ms 4,372 KB
testcase_93	AC	2 ms 4,368 KB
testcase_94	AC	2 ms 4,368 KB
testcase_95	AC	2 ms 4,368 KB
testcase_96	AC	2 ms 4,372 KB
testcase_97	AC	2 ms 4,372 KB
testcase_98	AC	3 ms 4,368 KB
testcase_99	AC	2 ms 4,368 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: 関数 ‘int main()’ 内:
main.cpp:162:46: 警告: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized]
  162 |     string goal = find_path(ky, kx, gy, gx, S);
      |                                              ^
main.cpp:143:29: 備考: ‘gx’ はここで定義されています
  143 |     int sy, sx, ky, kx, gy, gx;
      |                             ^~
main.cpp:162:46: 警告: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized]
  162 |     string goal = find_path(ky, kx, gy, gx, S);
      |                                              ^
main.cpp:143:25: 備考: ‘gy’ はここで定義されています
  143 |     int sy, sx, ky, kx, gy, gx;
      |                         ^~
main.cpp:162:46: 警告: ‘kx’ may be used uninitialized [-Wmaybe-uninitialized]
  162 |     string goal = find_path(ky, kx, gy, gx, S);
      |                                              ^
main.cpp:143:21: 備考: ‘kx’ はここで定義されています
  143 |     int sy, sx, ky, kx, gy, gx;
      |                     ^~
main.cpp:162:46: 警告: ‘ky’ may be used uninitialized [-Wmaybe-uninitialized]
  162 |     string goal = find_path(ky, kx, gy, gx, S);
      |                                              ^
main.cpp:143:17: 備考: ‘ky’ はここで定義されています
  143 |     int sy, sx, ky, kx, gy, gx;
      |                 ^~
main.cpp:159:50: 警告: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
  159 |     string find_key = find_path(sy, sx, ky, kx, S);
      |                                                  ^
main.cpp:143:13: 備考: ‘sx’ はここで定義されています
  143 |     int sy, sx, ky, kx, gy, gx;
      |             ^~
main.cpp:159:50: 警告: ‘sy’ may be used uninitialized [-Wmaybe-uninitialized]
  159 |     string find_key = find_path(sy, sx, ky, kx, S);
      |                                                  ^
main.cpp:143:9: 備考: ‘sy’ はここで定義されてい��

ソースコード

raw source code

// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
template<class T> using V = vector<T>;
using VI = V<int>;
using VL = V<ll>;
using VS = V<string>;
template<class T> using PQ = priority_queue<T, V<T>, greater<T>>;
using G = V<VI>;
template<class T> using WG = V<V<pair<int, T>>>;
#define overload4(_1,_2,_3,_4,name,...) name
#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll _=0;_<(n);++_)
#define rep2(i,n) for(ll i=0;i<(n);++i)
#define rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep4(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i=n-1;i>=0;--i)
#define rrep2(i,n) for(ll i=n-1;i>=0;--i)
#define rrep3(i,a,b) for(ll i=b-1;i>=a;--i)
#define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define inside(h,w,y,x) (unsigned(y)<h&&unsigned(x)<w)
#ifdef _DEBUG
#define line cout << "-----------------------------\n"
#define debug(...) print(__VA_ARGS__)
#else
#define line
#define debug
#endif
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 61;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; }return false; }
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; }return false; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T> inline istream& operator>>(istream& is, V<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T> inline V<T> vec(size_t a) { return V<T>(a); }
template<class T> inline V<T> defvec(T def, size_t a) { return V<T>(a, def); }
template<class T, class... Ts> inline auto vec(size_t a, Ts... ts) { return V<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts> inline auto defvec(T def, size_t a, Ts... ts) { return V<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }
template<class T> inline void print(const T& a) { cout << a << "\n"; }
template<class T, class... Ts> inline void print(const T& a, const Ts&... ts) { cout << a << " "; print(ts...); }
template<class T> inline void print(const V<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }
template<class T> inline void print(const V<V<T>>& v) { for (auto& a : v)print(a); }
template<class T> inline constexpr const T cum(const V<T>& a, int l, int r) { return 0 <= l && l <= r && r < a.size() ? a[r] - (l == 0 ? 0 : a[l - 1]) : 0; }//[l,r]
template<class T> inline constexpr const auto min(const T& v) { return *min_element(all(v)); }
template<class T> inline constexpr const auto max(const T& v) { return *max_element(all(v)); }
template<class T> inline V<T>& operator++(V<T>& v) { for (T& a : v)++a; return v; }
template<class T> inline V<T>& operator--(V<T>& v) { for (T& a : v)--a; return v; }
// clang-format on

const int grid_size = 60;  // 迷宮の大きさ
const int max_hp = 1500;   // 初期体力
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
string dir = "UDLR";

// 探知機の情報
struct enemy {
    int y, x, d, num;
    bool destroyed;
    enemy(int y, int x, int d, int num) {
        this->y = y, this->x = x, this->d = d;
        this->num = num;
        destroyed = false;
    }
};

// 範囲外かどうか
bool range_out(int y, int x) {
    if (y < 0 || y >= grid_size) return true;
    if (x < 0 || x >= grid_size) return true;
    return false;
}

// BFSによる経路探索
string find_path(int sy, int sx, int gy, int gx, vector<string>& S) {
    int siz = S.size();
    vector<vector<int>> dist(siz, vector<int>(siz, -1));
    dist[sy][sx] = 0;
    queue<pair<int, int>> q;
    q.emplace(sy, sx);
    while (!q.empty()) {
        pair<int, int> p = q.front();
        q.pop();
        int y = p.first, x = p.second;
        for (int k = 0; k < 4; k++) {
            int ny = y + dy[k], nx = x + dx[k];
            if (range_out(ny, nx)) continue;
            if (dist[ny][nx] != -1) continue;
            char cell = S[ny][nx];
            if (cell == '#' || cell == 'B' || cell == 'E') continue;
            dist[ny][nx] = dist[y][x] + 1;
            q.emplace(ny, nx);
        }
    }
    string res;
    if (dist[gy][gx] == -1) return res;
    int now_y = gy, now_x = gx, now_d = dist[gy][gx];
    while (now_y != sy || now_x != sx) {
        bool moved = false;
        for (int k = 0; k < 4; k++) {
            int new_y = now_y + dy[k], new_x = now_x + dx[k];
            if (range_out(new_y, new_x)) continue;
            if (dist[new_y][new_x] != now_d - 1) continue;
            now_y = new_y, now_x = new_x;
            now_d--;
            res.push_back(dir[k ^ 1]);
            moved = true;
            break;
        }
        assert(moved);
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    init();

    // 入力の受け取り
    int N, D, H;
    cin >> N >> D >> H;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];
    int M;
    cin >> M;
    vector<enemy> E;
    for (int i = 0; i < M; i++) {
        int y, x, d;
        cin >> y >> x >> d;
        E.emplace_back(y, x, d, i);
    }

    string ans;
    int sy, sx, ky, kx, gy, gx;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (S[i][j] == 'S') {
                sy = i, sx = j;
            }
            else if (S[i][j] == 'K') {
                ky = i, kx = j;
            }
            else if (S[i][j] == 'G') {
                gy = i, gx = j;
            }
        }
    }

    // 鍵の取得
    string find_key = find_path(sy, sx, ky, kx, S);
    ans += find_key;
    // 扉への移動
    string goal = find_path(ky, kx, gy, gx, S);
    ans += goal;
    for (auto c : ans) {
        cout << "M " << c << endl;
    }

    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード