結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:51:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 3,000 ms |
コード長 | 3,113 bytes |
コンパイル時間 | 3,996 ms |
コンパイル使用メモリ | 210,048 KB |
実行使用メモリ | 33,536 KB |
最終ジャッジ日時 | 2025-07-11 21:51:46 |
合計ジャッジ時間 | 5,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:141:24: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized] 141 | chmin(ans, d[gx][gy][i]); | ^ main.cpp:83:9: note: ‘gx’ was declared here 83 | int gx, gy; | ^~ main.cpp:141:28: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized] 141 | chmin(ans, d[gx][gy][i]); | ^ main.cpp:83:13: note: ‘gy’ was declared here 83 | int gx, gy; | ^~ In file included from /usr/include/c++/13/bits/memory_resource.h:47, from /usr/include/c++/13/string:58, from /usr/include/c++/13/bitset:52, from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52, from main.cpp:1: In constructor ‘constexpr std::_Head_base<_Idx, _Head, false>::_Head_base(_UHead&&) [with _UHead = int&; long unsigned int _Idx = 0; _Head = int]’, inlined from ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(_UHead&&, _UTail&& ...) [with _UHead = int&; _UTail = {int&, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = int; _Tail = {int, int}]’ at /usr/include/c++/13/tuple:293:38, inlined from ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int&, int}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {int, int, int}]’ at /usr/include/c++/13/tuple:891:54, inlined from ‘int main()’ at main.cpp:102:13: /usr/include/c++/13/tuple:201:11: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized] 201 | : _M_head_impl(std::forward<_UHead>(__h)) { } | ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:82:9: note: ‘sx’ was declared here 82 | int sx, sy
ソースコード
#include <bits/stdc++.h> using namespace std; #define CPP_STR(x) CPP_STR_I(x) #define CPP_CAT(x, y) CPP_CAT_I(x, y) #define CPP_STR_I(args...) #args #define CPP_CAT_I(x, y) x##y #define ASSERT(expr...) assert((expr)) using i8 = int8_t; using u8 = uint8_t; using i16 = int16_t; using u16 = uint16_t; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; using f32 = float; using f64 = double; // }}} constexpr i64 INF = 1'010'000'000'000'000'017LL; constexpr i64 MOD = 998244353LL; constexpr f64 EPS = 1e-12; constexpr f64 PI = 3.14159265358979323846; #define M5 100007 #define M9 1000000000 #define F first #define S second // util {{{ #define FOR(i, start, end) for (i64 i = (start), CPP_CAT(i, xxxx_end) = (end); i < CPP_CAT(i, xxxx_end); ++i) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() #define ll long long int #define VI vector<ll> #define VVI vector<VI> #define ISD true #define debug(x) \ if (ISD) \ cout << #x << ": " << x << endl template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) { if (comp(xmax, x)) { xmax = x; return true; } return false; } template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) { if (comp(x, xmin)) { xmin = x; return true; } return false; } int main() { ll H, W, M; cin >> H >> W >> M; vector<string> S(H); REP(i, H) cin >> S[i]; int sx, sy; int gx, gy; REP(i, H) REP(j, W) { if (S[i][j] == 'S') { sx = i; sy = j; } if (S[i][j] == 'G') { gx = i; gy = j; } } using P = tuple<int, int, int>; vector<VVI> d(H, VVI(W, VI(10, INF))); queue<P> que; que.push({sx, sy, 0}); // sから探索する d[sx][sy][0] = 0; int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; while (que.size() != 0) { // 幅優先探索 P state = que.front(); // 現在の状態 que.pop(); int x = get<0>(state); int y = get<1>(state); int t = get<2>(state); REP(k, 4) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || ny < 0 || nx >= H || ny >= W || S[nx][ny] == '#') continue; int nt = t; if ('1' <= S[nx][ny] && S[nx][ny] <= '9') { nt = S[nx][ny] - '0'; } if ('a' <= S[nx][ny] && S[nx][ny] <= 'z' && S[nx][ny] - 'a' + 1 != t) { continue; } if (d[nx][ny][nt] != INF) { continue; } d[nx][ny][nt] = d[x][y][t] + 1; que.push({nx, ny, nt}); } } ll ans = INF; REP(i, 10) { chmin(ans, d[gx][gy][i]); } if (ans == INF) { cout << -1 << endl; } else { cout << ans << endl; } }