結果
問題 |
No.3199 Key-Door Grid
|
ユーザー |
|
提出日時 | 2025-07-11 21:54:46 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 3,000 ms |
コード長 | 8,336 bytes |
コンパイル時間 | 1,755 ms |
コンパイル使用メモリ | 167,044 KB |
実行使用メモリ | 25,700 KB |
最終ジャッジ日時 | 2025-07-11 21:54:52 |
合計ジャッジ時間 | 5,294 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 37 |
コンパイルメッセージ
In member function ‘bool myclass::grid_base::isvalid(ll, ll) const’, inlined from ‘ll myclass::grid_base::operator()(ll, ll) const’ at main.cpp:240:15, inlined from ‘void solve()’ at main.cpp:326:10: main.cpp:250:41: warning: ‘si’ may be used uninitialized [-Wmaybe-uninitialized] 250 | return 0 <= i && 0 <= j && i < height && j < width; | ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~ main.cpp: In function ‘void solve()’: main.cpp:310:12: note: ‘si’ was declared here 310 | ll si, sj; | ^~ In member function ‘bool myclass::grid_base::isvalid(ll, ll) const’, inlined from ‘ll myclass::grid_base::operator()(ll, ll) const’ at main.cpp:240:15, inlined from ‘void solve()’ at main.cpp:326:10: main.cpp:250:55: warning: ‘sj’ may be used uninitialized [-Wmaybe-uninitialized] 250 | return 0 <= i && 0 <= j && i < height && j < width; | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~ main.cpp: In function ‘void solve()’: main.cpp:310:16: note: ‘sj’ was declared here 310 | ll si, sj; | ^~ In member function ‘bool myclass::grid_base::isvalid(ll, ll) const’, inlined from ‘ll myclass::grid_base::operator()(ll, ll) const’ at main.cpp:240:15, inlined from ‘void solve()’ at main.cpp:348:31: main.cpp:250:41: warning: ‘gi’ may be used uninitialized [-Wmaybe-uninitialized] 250 | return 0 <= i && 0 <= j && i < height && j < width; | ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~ main.cpp: In function ‘void solve()’: main.cpp:311:12: note: ‘gi’ was declared here 311 | ll gi, gj; | ^~ In member function ‘bool myclass::grid_base::isvalid(ll, ll) const’, inlined from ‘ll myclass::grid_base::operator()(ll, ll) const’ at main.cpp:240:15, inlined from ‘void solve()’ at main.cpp:348:31: main.cpp:25
ソースコード
#define MOD_IS_998 1 #if __has_include("template.hpp") #include "template.hpp" #else // template start #include <algorithm> #include <concepts> #include <cstdint> #include <iostream> #include <istream> #include <limits> #include <ostream> #include <queue> #include <random> #include <ranges> #include <set> #include <stdexcept> #include <string> #include <type_traits> #include <utility> #include <vector> #include <atcoder/modint.hpp> // often use #include <cassert> #include <ios> #include <map> using namespace std; using ll = long long; using pall = pair<ll, ll>; template<class T> using vec = vector<T>; template<class T> using veve = vec<vec<T>>; using vell = vec<ll>; using vest = vec<string>; using vebo = basic_string<bool>; using vevell = veve<ll>; template<class T> using mset = multiset<T>; template<class T> using priority_queue_ascend = priority_queue<T, vec<T>, greater<T>>; const ll inf = numeric_limits<ll>::max(); const string sp = " "; const string lf = "\n"; const auto &npos = string::npos; #ifdef MOD_IS_998 constexpr ll MOD = 998244353; #else constexpr ll MOD = 1e9 + 7; #endif const vec<pall> grid_move4 = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}}; const vec<pall> grid_move8 = [] { auto ret = grid_move4; ret.insert(ret.end(), {{-1, 1}, {-1, -1}, {1, -1}, {1, 1}}); return ret; }(); #define cont continue #define br break #define auot auto #define whlie while #define foR for #define cosnt const #define conts const auto &ciN = cin; auto &icn = cin; auto &icN = cin; constexpr bool ture = true; using namespace atcoder; using mint = static_modint<MOD>; #define times(N) \ static_assert(is_integral_v<decltype((N) + 0)>, \ "times(): N must be integral"); \ for(typedef decltype((N) + 0) _int; \ [[maybe_unused]] const _int _i : views::iota((_int)0, (N))) #define tiems times #define itmes times struct debug_stream { template<class T> debug_stream &operator<<([[maybe_unused]] const T &x) { #ifndef ONLINE_JUDGE clog << x; #endif return *this; } }; template<class T> concept out_stream = same_as<ostream, T> || same_as<debug_stream, T>; debug_stream clog_; #define clog clog_ template<int M> istream &operator>>(istream &in, static_modint<M> &i) { intmax_t tmp; in >> tmp; i = tmp; return in; } template<int M> decltype(auto) operator<<(out_stream auto &out, const static_modint<M> &i) { return out << i.val(); } template<class T, class U> istream &operator>>(istream &in, pair<T, U> &p) { return in >> p.first >> p.second; } template<class T, class U> decltype(auto) operator<<(out_stream auto &out, const pair<T, U> &p) { return out << p.first << sp << p.second; } template<class T> istream &operator>>(istream &in, vec<T> &v) { for(auto &&e : v) { in >> e; } return in; } namespace myinput { template<class... Ts> istream &in(Ts &...vecs) { static_assert(sizeof...(vecs) != 0, "myfunc::in(): At least one vector must be provided"); const set sizes = {vecs.size()...}; if(sizes.size() > 1) { throw invalid_argument("myfunc::in(): All vectors must have the same size"); } times(*sizes.begin()) { ((cin >> vecs[_i]), ...); } return cin; } } // namespace myinput using myinput::in; void out(ranges::range auto v, const string delim, out_stream auto &out = cout) { for(auto &&e : v) { out << e << delim; } } [[nodiscard]] const string &yesno(const bool cond, const string &yes = "Yes", const string &no = "No") noexcept { if(cond) return yes; return no; } // [mi, ma) [[nodiscard]] uint64_t randint(const uint64_t mi, const uint64_t ma) noexcept { static random_device seed; static mt19937_64 mt(seed()); if(mi > ma) [[unlikely]] return randint(ma, mi); if(mi == ma) [[unlikely]] return mi; const uint64_t w = ma - mi; uint64_t r; do { r = mt(); } while(mt.max() - mt.max() % w <= r); return r % w + mi; } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto min(T &&a, U &&b) noexcept { return std::min<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T, class U> requires common_with<T, U> [[nodiscard]] constexpr auto max(T &&a, U &&b) noexcept { return std::max<common_type_t<T, U>>(std::forward<T>(a), std::forward<U>(b)); } template<class T> [[nodiscard]] const T &min(const vec<T> &v) { return *ranges::min_element(v); } template<class T> [[nodiscard]] const T &max(const vec<T> &v) { return *ranges::max_element(v); } template<class... Args> [[nodiscard]] auto reduce(const ranges::range auto &v, Args... args) { return reduce(v.begin(), v.end(), args...); } [[nodiscard]] constexpr ll powll(ll a, ll b, const ll m = inf) { if(b < 0) [[unlikely]] throw invalid_argument("powll(): exponent less than zero"); if(m < 1) [[unlikely]] throw invalid_argument("powll(): modulo less than one"); a %= m; ll ret = 1; while(b) { if(b % 2) ret *= a, ret %= m; a *= a, a %= m; b /= 2; } return ret; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool mini(T &var, U &&val) noexcept { const bool cmp = var > val; if(cmp) var = val; return cmp; } template<class T, class U> requires assignable_from<T &, U> && totally_ordered_with<T, U> bool maxi(T &var, U &&val) noexcept { const bool cmp = var < val; if(cmp) var = val; return cmp; } namespace myclass { class [[nodiscard]] grid_base { public: grid_base(const ll h, const ll w) noexcept : height(h), width(w) {} [[nodiscard]] ll operator()(const ll i, const ll j) const noexcept { if(! isvalid(i, j)) return -1; return i * width + j; } [[nodiscard]] ll operator()(const pall &p) const noexcept { return (*this)(p.first, p.second); } protected: bool isvalid(const ll i, const ll j) const noexcept { return 0 <= i && 0 <= j && i < height && j < width; } const ll height, width; }; class [[nodiscard]] grid_seen : public myclass::grid_base { public: grid_seen(const ll h, const ll w) : grid_base(h, w) { visited = vebo(h * w, false); } [[nodiscard]] bool &seen(const ll i, const ll j) & { if(! isvalid(i, j)) [[unlikely]] throw out_of_range("grid::seen(): out of range"); return visited[i * width + j]; } [[nodiscard]] bool &seen(const pall &p) & { return seen(p.first, p.second); } private: vebo visited; }; } // namespace myclass using grid_lite = myclass::grid_base; using myclass::grid_seen; template<class T> auto erase_single(mset<T> &mset, T &&v) { const auto it = mset.find(v); if(it == mset.end()) [[unlikely]] throw invalid_argument("erase_single(): why v not in mset!?!?"); return mset.erase(it); } void solve(); // template end #endif int main(void) { cin.tie(nullptr); ios::sync_with_stdio(false); ll t = 1; // cin >> t; times(t) solve(); return 0; } bool isnumber(const char c) { return '0' <= c && c <= '9'; } void solve() { ll h, w, m; cin >> h >> w >> m; vest s(h); cin >> s; ll si, sj; ll gi, gj; vell dist(h * w * (m + 1), inf / 8); vebo sen(h * w * (m + 1), false); for(intmax_t i = 0; i < intmax_t(h); i++) { for(intmax_t j = 0; j < intmax_t(w); j++) { if(s[i][j] == 'S') { si = i, sj = j; } if(s[i][j] == 'G') { gi = i, gj = j; } } } queue<ll> q; const auot g = grid_lite(h, w); q.push(g(si, sj)); dist[g(si, sj)] = 0; while(q.size()) { const auto e = q.front(); q.pop(); if(sen[e]) cont; sen[e] = ture; const ll i = e % (h * w) / w, j = e % (h * w) % w; for(const auto &[di, dj] : grid_move4) { const pall ne = {di + i, dj + j}; if(g(ne) < 0) cont; const char next_tile = s[ne.first][ne.second]; if(next_tile == '#') cont; const ll next_key = isnumber(next_tile) ? next_tile - '0' : e / (h * w); if(isalpha(next_tile) && next_tile >= 'a' && next_key != next_tile - 'a' + 1) cont; const ll ne_val = next_key * h * w + g(ne); if(sen[ne_val]) cont; if(not mini(dist[ne_val], dist[e] + 1)) cont; q.push(ne_val); } } ll ans = inf / 10; times(m + 1) mini(ans, dist[g(gi, gj) + _i * w * h]); if(ans > inf / 100) ans = -1; cout << ans << lf; for(intmax_t i = 0; i < intmax_t(m + 1); i++) { for(intmax_t j = 0; j < intmax_t(h); j++) { for(intmax_t k = 0; k < intmax_t(w); k++) { const ll d = dist[i * h * w + j * w + k]; clog << (d > inf / 100 ? -1 : d) << sp; } clog << lf; } clog << lf; } }