結果
問題 |
No.367 ナイトの転身
|
ユーザー |
![]() |
提出日時 | 2016-12-02 22:32:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 2,589 bytes |
コンパイル時間 | 1,635 ms |
コンパイル使用メモリ | 65,688 KB |
実行使用メモリ | 817,908 KB |
最終ジャッジ日時 | 2024-11-27 17:44:26 |
合計ジャッジ時間 | 27,988 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 15 TLE * 7 MLE * 5 |
ソースコード
#include <iostream> #include <queue> #include <list> using namespace std; #define N 0 #define B 1 #define ull unsigned long long int struct Data { short int x, y, c, s; }; queue<Data> q; int h, w, x, y; int state = N; bool*** f; int c = 1; void pushQ(int x, int y, int c, int s) { Data* t = new Data(); t->x = x, t->y = y, t->c = c, t->s = s; q.push(*t); } void pushqueue() { if (state) { // state = B if (x - 1 >= 0) { if (y - 1 >= 0) { if (!f[y-1][x-1][state]) { pushQ(x - 1, y - 1, c, state); } } if (y + 1 < h) { if (!f[y+1][x-1][state]) { pushQ(x - 1, y + 1, c, state); } } } if (x + 1 < w) { if (y - 1 >= 0) { if (!f[y-1][x+1][state]) { pushQ(x + 1, y - 1, c, state); } } if (y + 1 < h) { if (!f[y+1][x+1][state]) { pushQ(x + 1, y + 1, c, state); } } } } else { // state = N if (x - 2 >= 0) { if (y - 1 >= 0) { if (!f[y-1][x-2][state]) { pushQ(x - 2, y - 1, c, state); } } if (y + 1 < h) { if (!f[y+1][x-2][state]) { pushQ(x - 2, y + 1, c, state); } } } if (x - 1 >= 0) { if (y - 2 >= 0) { if (!f[y-2][x-1][state]) { pushQ(x - 1, y - 2, c, state); } } if (y + 2 < h) { if (!f[y+2][x-1][state]) { pushQ(x - 1, y + 2, c, state); } } } if (x + 1 < w) { if (y - 2 >= 0) { if (!f[y-2][x+1][state]) { pushQ(x + 1, y - 2, c, state); } } if (y + 2 < h) { if (!f[y+2][x+1][state]) { pushQ(x + 1, y + 2, c, state); } } } if (x + 2 < w) { if (y - 1 >= 0) { if (!f[y-1][x+2][state]) { pushQ(x + 2, y - 1, c, state); } } if (y + 1 < h) { if (!f[y+1][x+2][state]) { pushQ(x + 2, y + 1, c, state); } } } } } void popq() { Data t = q.front(); q.pop(); x = t.x, y = t.y, c = t.c, state = t.s; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> h >> w; char** d = new char*[h]; f = new bool**[h]; for (int i = 0; i < h; ++i) { d[i] = new char[w]; f[i] = new bool*[w]; for (int j = 0; j < w; ++j) { cin >> d[i][j]; f[i][j] = new bool[2]; if (d[i][j] == 'S') { d[i][j] = '.'; f[i][j][N] = true; f[i][j][B] = false; y = i; x = j; } else { f[i][j][N] = false; f[i][j][B] = false; } } } pushqueue(); while (!(q.empty())) { popq(); f[y][x][state] = true; if (d[y][x] == 'G') { cout << c << endl; goto end; } else if (d[y][x] == 'R') { state ^= 1; // stateが1なら0、0なら1 } ++c; pushqueue(); } cout << -1 << endl; end: return 0; }