結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
![]() |
提出日時 | 2025-07-11 21:43:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 90 ms / 3,000 ms |
コード長 | 2,141 bytes |
コンパイル時間 | 3,543 ms |
コンパイル使用メモリ | 309,800 KB |
実行使用メモリ | 13,740 KB |
最終ジャッジ日時 | 2025-07-11 21:43:13 |
合計ジャッジ時間 | 6,166 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:34:15: warning: ‘ti’ may be used uninitialized [-Wmaybe-uninitialized] 34 | int si, sj, ti, tj; | ^~ main.cpp:34:19: warning: ‘tj’ may be used uninitialized [-Wmaybe-uninitialized] 34 | int si, sj, ti, tj; | ^~ In file included from /usr/include/c++/13/bits/uses_allocator_args.h:38, from /usr/include/c++/13/bits/memory_resource.h:41, 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, int}; <template-parameter-2-3> = void; long unsigned int _Idx = 0; _Head = int; _Tail = {int, 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, int}; bool _Valid = true; typename std::enable_if<_TCC<_Valid>::__is_implicitly_constructible<_UElements ...>(), bool>::type <anonymous> = true; _Elements = {int, int, int, int}]’ at /usr/include/c++/13/tuple:891:54, inlined from ‘constexpr decltype (::new(void*(0)) _Tp) std::construct_at(_Tp*, _Args&& ...) [with _Tp = tuple<int, int, int, int>; _Args = {int&, int&, int, int}]’ at /usr/include/c++/13/bits/stl_construct.h:97:14, inlined from ‘static constexpr void std::allocator_traits<std::allocator<_CharT> >::construct(allocator_type&, _Up*, _Args&& ...) [with _Up = std::tuple<int, int, int, int>; _Args = {int&, int&, int, int}; _Tp = std::tuple<int, int, int, int>]’ at /usr/include/c++/13/bits/alloc_traits.h:540
ソースコード
#include<bits/stdc++.h> namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include<atcoder/all> #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair<int,int>; using VI = vector<int>; using VVI = vector<VI>; using VL = vector<ll>; using VVL = vector<VL>; const int di[] = {1, 0, -1, 0}; const int dj[] = {0, 1, 0, -1}; int dist[500][500][10]; } int main() { ios::sync_with_stdio(false); cin.tie(0); int h, w, m; cin >> h >> w >> m; constexpr int INF = 1001001001; rep(i, h) rep(j, w) rep(k, m + 1) dist[i][j][k] = INF; vector<string> s(h); rep(i, h) cin >> s[i]; int si, sj, ti, tj; rep(i, h) rep(j, w) { if (s[i][j] == 'S') { si = i, sj = j; s[i][j] = '.'; } else if (s[i][j] == 'G') { ti = i, tj = j; s[i][j] = '.'; } } deque<tuple<int, int, int, int>> q; dist[si][sj][0] = 0; q.emplace_back(si, sj, 0, 0); auto idxchk = [&](int i, int j) { return 0 <= i && i < h && 0 <= j && j < w; }; while (q.size()) { auto [i, j, k, d] = q.front(); q.pop_front(); if (dist[i][j][k] != d) continue; if ('1' <= s[i][j] && s[i][j] <= '9' && k != s[i][j] - '0') { int nk = s[i][j] - '0'; if (chmin(dist[i][j][nk], d)) q.emplace_front(i, j, nk, d); continue; } else if ('a' <= s[i][j] && s[i][j] <= 'i' && k != s[i][j] - 'a' + 1) { continue; } rep(dir, 4) { int ni = i + di[dir], nj = j + dj[dir]; if (!idxchk(ni, nj) || s[ni][nj] == '#') continue; if (chmin(dist[ni][nj][k], d + 1)) q.emplace_back(ni, nj, k, d + 1); } } int ans = INF; rep(k, m + 1) chmin(ans, dist[ti][tj][k]); if (ans == INF) ans = -1; cout << ans << '\n'; }