結果
問題 | No.367 ナイトの転身 |
ユーザー |
![]() |
提出日時 | 2017-06-23 15:18:35 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 1,586 bytes |
コンパイル時間 | 707 ms |
コンパイル使用メモリ | 68,340 KB |
実行使用メモリ | 8,388 KB |
最終ジャッジ日時 | 2024-10-03 04:10:33 |
合計ジャッジ時間 | 2,121 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 27 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:43:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 43 | scanf(" %c", &c); | ~~~~~^~~~~~~~~~~
ソースコード
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> using namespace std; #define FOR(i,a,b) for (ll i = (a); i < (b); i++) #define REP(i,n) FOR(i,0,n) typedef long long ll; const ll INF = 1ll<<29; const ll MOD = 1000000007; const double EPS = 1e-10; int d[501][501][2]; int dx[2][8] = {{-2,-2,-1,-1,1,1,2,2},{-1,-1,1,1}}; int dy[2][8] = {{-1,1,-2,2,-2,2,-1,1},{-1,1,-1,1}}; int map[501][501]; int f[501][501][2]; int f_f[2] = {8,4}; int main(){ REP(i,501){ REP(j,501){ REP(k,2){ d[i][j][k] = 100000; } } } queue<int> q; int h, w; cin >> h >> w; int g_x, g_y; REP(i,h){ REP(j,w){ char c; scanf(" %c", &c); if (c == 'S'){ d[i][j][0] = 0; d[i][j][1] = 0; f[i][j][0] = 1; f[i][j][1] = 1; q.push(j); q.push(i);} if (c == 'G'){ g_x = j; g_y = i;} if (c == 'R'){ map[i][j] = 1;} } } q.push(0); while (!q.empty()){ int x = q.front(); q.pop(); int y = q.front(); q.pop(); int flag = q.front(); q.pop(); int nf; REP(i,f_f[flag]){ int x1 = x+dx[flag][i]; int y1 = y+dy[flag][i]; if (x1 >= 0 && x1 < w && y1 >= 0 && y1 < h){ if (map[y1][x1] == 1) nf = !flag; else nf = flag; if (f[y1][x1][nf] == 0){ q.push(x1); q.push(y1); if (nf) q.push(1); else q.push(0); d[y1][x1][nf] = d[y][x][flag]+1; f[y1][x1][nf] = 1; } } } } REP(i,h){ REP(j,w){ if (d[i][j][0] == 100000 && d[i][j][1] == 100000){ d[i][j][0] = -1; d[i][j][1] = -1; } } } cout << min(d[g_y][g_x][0], d[g_y][g_x][1]) << endl; return 0; }