結果
| 問題 | No.367 ナイトの転身 |
| ユーザー |
 izryt(趣味)
|
| 提出日時 | 2016-08-05 01:57:25 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 36 ms / 2,000 ms |
| コード長 | 3,675 bytes |
| コンパイル時間 | 964 ms |
| コンパイル使用メモリ | 97,464 KB |
| 実行使用メモリ | 7,748 KB |
| 最終ジャッジ日時 | 2024-11-07 00:10:23 |
| 合計ジャッジ時間 | 2,168 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,820 KB |
| testcase_02 | AC | 2 ms
6,820 KB |
| testcase_03 | AC | 3 ms
6,816 KB |
| testcase_04 | AC | 3 ms
6,820 KB |
| testcase_05 | AC | 3 ms
6,820 KB |
| testcase_06 | AC | 4 ms
7,616 KB |
| testcase_07 | AC | 3 ms
6,824 KB |
| testcase_08 | AC | 2 ms
6,820 KB |
| testcase_09 | AC | 3 ms
6,820 KB |
| testcase_10 | AC | 29 ms
7,748 KB |
| testcase_11 | AC | 36 ms
7,692 KB |
| testcase_12 | AC | 25 ms
7,056 KB |
| testcase_13 | AC | 18 ms
6,856 KB |
| testcase_14 | AC | 23 ms
6,960 KB |
| testcase_15 | AC | 4 ms
6,888 KB |
| testcase_16 | AC | 22 ms
7,048 KB |
| testcase_17 | AC | 5 ms
6,816 KB |
| testcase_18 | AC | 6 ms
6,816 KB |
| testcase_19 | AC | 8 ms
6,820 KB |
| testcase_20 | AC | 5 ms
6,816 KB |
| testcase_21 | AC | 9 ms
6,820 KB |
| testcase_22 | AC | 3 ms
6,820 KB |
| testcase_23 | AC | 3 ms
6,816 KB |
| testcase_24 | AC | 3 ms
6,816 KB |
| testcase_25 | AC | 3 ms
6,820 KB |
| testcase_26 | AC | 3 ms
6,816 KB |
コンパイルメッセージ
In function 'T& min(T&, T&) [with T = long long int]',
inlined from 'int main()' at main.cpp:137:17:
main.cpp:38:41: warning: 'gx' may be used uninitialized [-Wmaybe-uninitialized]
38 | template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
| ~^~
main.cpp: In function 'int main()':
main.cpp:80:21: note: 'gx' was declared here
80 | int sx, sy, gy, gx;
| ^~
In function 'T& min(T&, T&) [with T = long long int]',
inlined from 'int main()' at main.cpp:137:17:
main.cpp:38:41: warning: 'gy' may be used uninitialized [-Wmaybe-uninitialized]
38 | template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
| ~^~
main.cpp: In function 'int main()':
main.cpp:80:17: note: 'gy' was declared here
80 | int sx, sy, gy, gx;
| ^~
main.cpp:93:21: warning: 'sy' may be used uninitialized [-Wmaybe-uninitialized]
93 | dist[0][sy][sx] = 0;
| ~~~~~~~~~~~~~~~~^~~
main.cpp:80:13: note: 'sy' was declared here
80 | int sx, sy, gy, gx;
| ^~
main.cpp:93:21: warning: 'sx' may be used uninitialized [-Wmaybe-uninitialized]
93 | dist[0][sy][sx] = 0;
| ~~~~~~~~~~~~~~~~^~~
main.cpp:80:9: note: 'sx' was declared here
80 | int sx, sy, gy, gx;
| ^~
ソースコード
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
using namespace std;
#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define int long long
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}
const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;
struct data {
int t, y, x;
data(int t, int y, int x):t(t),y(y),x(x){}
};
char fld[502][502];
int dist[2][502][502];
int dx0[8] = {-2, -1, 1, 2, -2, -1, 1, 2}, dy0[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dx1[4] = {-1, 1, -1, 1}, dy1[4] = {-1, -1, 1, 1};
int H, W;
bool inside(int y, int x)
{
return (0 <= y && y < H && 0 <= x && x < W);
}
signed main()
{
cin >> H >> W;
for (int i = 0; i < 2; ++i) {
for (int j = 0; j < H; ++j) {
for (int k = 0; k < W; ++k) {
dist[i][j][k] = inf;
}
}
}
int sx, sy, gy, gx;
for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) {
cin >> fld[i][j];
if (fld[i][j] == 'S') {
sy = i, sx = j;
} else if (fld[i][j] == 'G') {
gy = i, gx = j;
}
}
queue<data> q;
q.push(data(0, sy, sx));
dist[0][sy][sx] = 0;
while (q.size()) {
data d = q.front(); q.pop();
if (d.t == 0) {
for (int i = 0; i < 8; ++i) {
int ny = d.y + dy0[i], nx = d.x + dx0[i];
if (!inside(ny, nx)) continue;
if (fld[ny][nx] == 'R') {
if (dist[0][d.y][d.x] + 1 < dist[1][ny][nx]) {
dist[1][ny][nx] = dist[0][d.y][d.x] + 1;
q.push(data(1, ny, nx));
}
} else {
if (dist[0][d.y][d.x] + 1 < dist[0][ny][nx]) {
dist[0][ny][nx] = dist[0][d.y][d.x] + 1;
q.push(data(0, ny, nx));
}
}
}
} else {
for (int i = 0; i < 4; ++i) {
int ny = d.y + dy1[i], nx = d.x + dx1[i];
if (!inside(ny, nx)) continue;
if (fld[ny][nx] == 'R') {
if (dist[1][d.y][d.x] + 1 < dist[0][ny][nx]) {
dist[0][ny][nx] = dist[1][d.y][d.x] + 1;
q.push(data(0, ny, nx));
}
} else {
if (dist[1][d.y][d.x] + 1 < dist[1][ny][nx]) {
dist[1][ny][nx] = dist[1][d.y][d.x] + 1;
q.push(data(1, ny, nx));
}
}
}
}
}
int mi = min(dist[0][gy][gx], dist[1][gy][gx]);
cout << (mi == inf ? -1 : mi) << endl;
}