結果
| 問題 |
No.3199 Key-Door Grid
|
| ユーザー |
👑  potato167
|
| 提出日時 | 2025-07-12 18:58:56 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 95 ms / 3,000 ms |
| コード長 | 6,625 bytes |
| コンパイル時間 | 2,215 ms |
| コンパイル使用メモリ | 206,968 KB |
| 実行使用メモリ | 14,464 KB |
| 最終ジャッジ日時 | 2025-07-12 18:59:01 |
| 合計ジャッジ時間 | 4,836 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 37 |
コンパイルメッセージ
c.cpp: In function ‘void solve()’:
c.cpp:59:41: warning: ‘gx’ may be used uninitialized [-Wmaybe-uninitialized]
c.cpp:25:17: note: ‘gx’ was declared here
c.cpp:59:45: warning: ‘gy’ may be used uninitialized [-Wmaybe-uninitialized]
c.cpp:25:21: note: ‘gy’ was declared here
In file included from /usr/include/c++/13/bits/memory_resource.h:47,
from /usr/include/c++/13/vector:80,
from /Users/Shared/po167_library/ds/Dequq.hpp:2:
In constructor ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(std::_Tuple_impl<_Idx, _Head, _Tail ...>&&) [with long unsigned int _Idx = 1; _Head = int; _Tail = {int}]’,
inlined from ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(std::_Tuple_impl<_Idx, _Head, _Tail ...>&&) [with long unsigned int _Idx = 0; _Head = int; _Tail = {int, int}]’ at /usr/include/c++/13/tuple:302:7,
inlined from ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(std::tuple< <template-parameter-1-1> >&&) [with _Elements = {int, int, int}]’ at /usr/include/c++/13/tuple:903:17,
inlined from ‘void po167::Deque<T>::emplace_back(Args&& ...) [with Args = {std::tuple<int, int, int>}; T = std::tuple<int, int, int>]’ at /Users/Shared/po167_library/ds/Dequq.hpp:101:9,
inlined from ‘void po167::Deque<T>::push_back(T&&) [with T = std::tuple<int, int, int>]’ at /Users/Shared/po167_library/ds/Dequq.hpp:25:41,
inlined from ‘void solve()’ at c.cpp:32:16:
/usr/include/c++/13/tuple:302:7: warning: ‘sx’ may be used uninitialized [-Wmaybe-uninitialized]
302 | _Tuple_impl(_Tuple_impl&&) = default;
| ^~~~~~~~~~~
c.cpp: In function ‘void solve()’:
c.cpp:25:9: note: ‘sx’ was declared here
In constructor ‘constexpr std::_Tuple_impl<_Idx, _Head>::_Tuple_impl(std::_Tuple_impl<_Idx, _Head>&&) [with long unsigned int _Idx = 2; _Head = int]’,
inlined from ‘constexpr std::_Tuple_impl<_Idx, _Head, _Tail ...>::_Tuple_impl(std:
ソースコード
//#include "po167_library/ds/Dequq.hpp"
//
//#include <bits/stdc++.h>
//using namespace std;
//#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
//const int INF = 2100000000;
//template<class T> bool chmin(T &a, T b){return (a > b ? a = b, 1 : 0);}
//
//void solve();
//// POP'N ROLL MUSIC / TOMOO
//int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int t = 1;
// // cin >> t;
// rep(i, 0, t) solve();
//}
//
//void solve(){
// int H, W, M;
// cin >> H >> W >> M;
// vector<string> S(H);
// rep(i, 0, H) cin >> S[i];
// int sx, sy, gx, gy;
// rep(i, 0, H) rep(j, 0, W){
// if (S[i][j] == 'S') sx = i, sy = j;
// if (S[i][j] == 'G') gx = i, gy = j;
// }
// vector dp(M + 1, vector(H, vector<int>(W, INF)));
// po167::Deque<tuple<int, int, int>> q;
// q.push_back({0, sx, sy});
// dp[0][sx][sy] = 0;
// vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
// while (!q.empty()){
// auto [c, x, y] = q.front();
// q.pop_front();
// if ('1' <= S[x][y] && S[x][y] <= '9' && S[x][y] != (char)('0' + c)){
// int d = S[x][y] - '0';
// if (dp[d][x][y] == INF){
// dp[d][x][y] = dp[c][x][y];
// q.push_front({d, x, y});
// }
// continue;
// }
// if ('a' <= S[x][y] && S[x][y] <= 'z' && S[x][y] != (char)('a' + c - 1)) continue;
// rep(k, 0, 4){
// int s = dx[k] + x;
// int t = dy[k] + y;
// if (s < 0 || H <= s || t < 0 || W <= t) continue;
// if (S[s][t] == '#') continue;
// if (chmin(dp[c][s][t], dp[c][x][y] + 1)){
// q.push_back({c, s, t});
// continue;
// }
// }
// }
// int ans = INF;
// rep(i, 0, M + 1) chmin(ans, dp[i][gx][gy]);
// if (ans == INF) ans = -1;
// cout << ans << "\n";
//}
#line 2 "/Users/Shared/po167_library/ds/Dequq.hpp"
#include <vector>
#include <cassert>
namespace po167{
// GPT 作
template<typename T>
struct Deque {
Deque()
: _cap(8), _size(0), _head(0)
{
_data = static_cast<T*>(operator new[](sizeof(T) * _cap));
}
~Deque() {
clear();
operator delete[](_data);
}
// 要素数
int size() const { return _size; }
bool empty() const { return _size == 0; }
// 前後に要素を追加
void push_back(const T& v) { emplace_back(v); }
void push_back(T&& v) { emplace_back(std::move(v)); }
void push_front(const T& v) { emplace_front(v); }
void push_front(T&& v) { emplace_front(std::move(v)); }
// 前後から取り出し
void pop_back() {
assert(!empty());
int idx = (_head + _size - 1) & (_cap - 1);
_data[idx].~T();
--_size;
}
void pop_front() {
assert(!empty());
_data[_head].~T();
_head = ( _head + 1 ) & (_cap - 1);
--_size;
}
// 前後の参照
T& front() {
assert(!empty());
return _data[_head];
}
T& back() {
assert(!empty());
int idx = (_head + _size - 1) & (_cap - 1);
return _data[idx];
}
// 添字アクセス (0 ≤ i < size())
T& operator[](int i) {
assert(i >= 0 && i < _size);
return _data[( _head + i ) & (_cap - 1)];
}
const T& operator[](int i) const {
assert(i >= 0 && i < _size);
return _data[( _head + i ) & (_cap - 1)];
}
// 全要素をクリア
void clear() {
for(int i = 0; i < _size; i++){
int idx = (_head + i) & (_cap - 1);
_data[idx].~T();
}
_size = 0;
_head = 0;
}
private:
T* _data;
int _cap; // 必ず2のべき乗
int _size;
int _head; // 先頭要素のインデックス
// 空きがなければ拡張
void ensure_capacity() {
if (_size < _cap) return;
int new_cap = _cap << 1;
T* new_data = static_cast<T*>(operator new[](sizeof(T) * new_cap));
// 要素を head から順にコピー
for(int i = 0; i < _size; i++){
new (&new_data[i]) T(std::move((*this)[i]));
(*this)[i].~T();
}
operator delete[](_data);
_data = new_data;
_cap = new_cap;
_head = 0;
}
// 前後に emplace
template<typename... Args>
void emplace_back(Args&&... args) {
ensure_capacity();
int idx = (_head + _size) & (_cap - 1);
new(&_data[idx]) T(std::forward<Args>(args)...);
++_size;
}
template<typename... Args>
void emplace_front(Args&&... args) {
ensure_capacity();
_head = (_head - 1) & (_cap - 1);
new(&_data[_head]) T(std::forward<Args>(args)...);
++_size;
}
};
}
#line 2 "c.cpp"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
const int INF = 2100000000;
template<class T> bool chmin(T &a, T b){return (a > b ? a = b, 1 : 0);}
void solve();
// POP'N ROLL MUSIC / TOMOO
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
// cin >> t;
rep(i, 0, t) solve();
}
void solve(){
int H, W, M;
cin >> H >> W >> M;
vector<string> S(H);
rep(i, 0, H) cin >> S[i];
int sx, sy, gx, gy;
rep(i, 0, H) rep(j, 0, W){
if (S[i][j] == 'S') sx = i, sy = j;
if (S[i][j] == 'G') gx = i, gy = j;
}
vector dp(M + 1, vector(H, vector<int>(W, INF)));
po167::Deque<tuple<int, int, int>> q;
q.push_back({0, sx, sy});
dp[0][sx][sy] = 0;
vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};
while (!q.empty()){
auto [c, x, y] = q.front();
q.pop_front();
if ('1' <= S[x][y] && S[x][y] <= '9' && S[x][y] != (char)('0' + c)){
int d = S[x][y] - '0';
if (dp[d][x][y] == INF){
dp[d][x][y] = dp[c][x][y];
q.push_front({d, x, y});
}
continue;
}
if ('a' <= S[x][y] && S[x][y] <= 'z' && S[x][y] != (char)('a' + c - 1)) continue;
rep(k, 0, 4){
int s = dx[k] + x;
int t = dy[k] + y;
if (s < 0 || H <= s || t < 0 || W <= t) continue;
if (S[s][t] == '#') continue;
if (chmin(dp[c][s][t], dp[c][x][y] + 1)){
q.push_back({c, s, t});
continue;
}
}
}
int ans = INF;
rep(i, 0, M + 1) chmin(ans, dp[i][gx][gy]);
if (ans == INF) ans = -1;
cout << ans << "\n";
}