結果
問題 | No.367 ナイトの転身 |
ユーザー | Drafear |
提出日時 | 2016-04-29 23:04:33 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 2,659 bytes |
コンパイル時間 | 1,569 ms |
コンパイル使用メモリ | 164,700 KB |
実行使用メモリ | 17,512 KB |
最終ジャッジ日時 | 2023-07-27 18:56:38 |
合計ジャッジ時間 | 3,181 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 2 ms
4,384 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 71 ms
17,512 KB |
testcase_11 | AC | 103 ms
17,480 KB |
testcase_12 | AC | 48 ms
8,948 KB |
testcase_13 | AC | 39 ms
8,868 KB |
testcase_14 | AC | 42 ms
8,668 KB |
testcase_15 | AC | 3 ms
4,380 KB |
testcase_16 | AC | 39 ms
8,144 KB |
testcase_17 | AC | 5 ms
4,376 KB |
testcase_18 | AC | 8 ms
4,376 KB |
testcase_19 | AC | 12 ms
4,820 KB |
testcase_20 | AC | 6 ms
4,376 KB |
testcase_21 | AC | 12 ms
4,768 KB |
testcase_22 | AC | 2 ms
4,376 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 3 ms
4,376 KB |
testcase_25 | AC | 2 ms
4,376 KB |
testcase_26 | AC | 2 ms
4,380 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:107:34: warning: ‘gy’ may be used uninitialized in this function [-Wmaybe-uninitialized] REP(i, 2) ans = min(ans, dist[gy][gx][i]); ^ main.cpp:107:38: warning: ‘gx’ may be used uninitialized in this function [-Wmaybe-uninitialized] REP(i, 2) ans = min(ans, dist[gy][gx][i]); ^ main.cpp:89:62: warning: ‘sy’ may be used uninitialized in this function [-Wmaybe-uninitialized] priority_queue<Node, vector<Node>, greater<Node> > Q; Q.push({sx, sy, 0, 0}); ~~~~~~^~~~~~~~~~~~~~~~ main.cpp:89:62: warning: ‘sx’ may be used uninitialized in this function [-Wmaybe-uninitialized]
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; typedef pair<ll, ll> P; #define EACH(i,a) for (auto& i : a) #define FOR(i,a,b) for (ll i=(a);i<(b);i++) #define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--) #define REP(i,n) for (ll i=0;i<(n);i++) #define RREP(i,n) for (ll i=(n)-1;i>=0;i--) #define debug(x) cout<<#x<<": "<<x<<endl #define pb push_back #define ALL(a) (a).begin(),(a).end() const ll linf = 1e18; const int inf = 1e9; const double eps = 1e-12; const double pi = acos(-1); template<typename T> istream& operator>>(istream& is, vector<T>& vec) { EACH(x,vec) is >> x; return is; } /* template<class... T> ostream& operator<<(ostream& os, tuple<T...>& t) { for (size_t i = 0; i < tuple_size< tuple<T...> >::value; ++i) { if (i) os << " "; os << get<0>(t); } return os; } */ template<typename T> ostream& operator<<(ostream& os, vector<T>& vec) { REP(i,vec.size()) { if (i) os << " "; os << vec[i]; } return os; } template<typename T> ostream& operator<<(ostream& os, vector< vector<T> >& vec) { REP(i,vec.size()) { if (i) os << endl; os << vec[i]; } return os; } struct Node { int x, y, mode, cost; }; bool operator>(const Node& n1, const Node& n2) { return n1.cost > n2.cost; } int H, W; vector<string> m; bool inRange(int x, int y) { return 0 <= x && x < W && 0 <= y && y < H; } vector< vector<P> > nxt = { {{1, 2}, {2, 1}, {1, -2}, {2, -1}, {-1, 2}, {-2, 1}, {-1, -2}, {-2, -1}}, {{1, 1}, {1, -1}, {-1, 1}, {-1, -1}}, }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); cin >> H >> W; m.resize(H); cin >> m; int sx, sy, gx, gy; REP(y, H) REP(x, W) { if (m[y][x] == 'S') { m[y][x] = '.'; sx = x, sy = y; } else if (m[y][x] == 'G') { m[y][x] = '.'; gx = x, gy = y; } } vector< vector< vector<int> > > dist(H, vector< vector<int> >(W, vector<int>(2, inf))); priority_queue<Node, vector<Node>, greater<Node> > Q; Q.push({sx, sy, 0, 0}); while ( !Q.empty() ) { Node node = Q.top(); Q.pop(); int x = node.x, y = node.y, cost = node.cost, mode = node.mode; // cout << x << " " << y << " " << mode << " " << cost << endl; if (cost > dist[y][x][mode]) continue; REP(i, nxt[mode].size()) { int nx = x + nxt[mode][i].first; int ny = y + nxt[mode][i].second; if ( !inRange(nx, ny) ) continue; int nm = m[ny][nx] == 'R' ? !mode : mode; if ( cost+1 < dist[ny][nx][nm] ) { dist[ny][nx][nm] = cost+1; Q.push({nx, ny, nm, dist[ny][nx][nm]}); } } } int ans = inf; REP(i, 2) ans = min(ans, dist[gy][gx][i]); if (ans == inf) cout << -1 << endl; else cout << ans << endl; }