結果
問題 | No.424 立体迷路 |
ユーザー | ramia777 |
提出日時 | 2022-05-22 13:01:21 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 3,963 bytes |
コンパイル時間 | 770 ms |
コンパイル使用メモリ | 94,296 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-20 12:29:39 |
合計ジャッジ時間 | 1,529 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 2 ms
5,376 KB |
testcase_16 | AC | 2 ms
5,376 KB |
testcase_17 | AC | 2 ms
5,376 KB |
testcase_18 | AC | 2 ms
5,376 KB |
testcase_19 | AC | 2 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 1 ms
5,376 KB |
testcase_22 | AC | 2 ms
5,376 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 2 ms
5,376 KB |
ソースコード
// yukicodr // No.424 立体迷路 //#include "stdafx.h" #include <iostream> #include <vector> #include <list>//list #include <set> //tree #include <map> //連想配列 #include <unordered_set> //hash #include <unordered_map> //hash #include <algorithm> #include <iomanip> using namespace std; #define START (0) #define RIGHT (1) #define UP (2) #define LEFT (3) #define DOWN (4) //二次元可変配列 vector <vector <int>> mass; vector <vector <int>> memo; int H,W; int sx, sy, gx, gy; typedef struct DIR{ int dx; int dy; }DIR; DIR dir[8] = { //dx,dy 0, 1, //0 -1, 0, //1 0,-1, //2 1, 0, //3 0, 2, //4 -2, 0, //5 0,-2, //6 2, 0, //7 }; int ans = 0; char b[100][100]; char _b[100][100]; void printM(int x0, int y0, int nx, int ny, int dir_index) { cout << "x=" << x0 << ",y=" << y0 << ",nx=" << nx << ",ny=" << ny << ",dir_index=" << dir_index <<endl; for (int x = 1; x <= H; x++) { for (int y = 1; y <= W; y++) { cout << _b[x][y] ; } cout << endl; } cout << endl; } void _printM(void) { for (int x = 1; x <= H; x++) { for (int y = 1; y <= W; y++) { _b[x][y]='0'; } } } //今いる座標 x, y void solve(int x, int y) { int nx, ny; if (1 == ans) return; if ((x == sx) && (y == sy)) { ans = 1; return;//たどり着いた } int dir_index = 0; do { if (ans) break; //次に行く座標 nx = x + dir[dir_index].dx; ny = y + dir[dir_index].dy; //printM(x, y, nx, ny, dir_index); //次に行く座標が迷路枠内であれば(nxがH制約、nyがW制約であることに注意) if ((nx >= 1 && nx <= H) && (ny >= 1 && ny <= W) && (_b[nx][ny] != '1')) { switch (dir_index) { case 0: case 1: case 2: case 3: if ((abs(b[x][y] - b[nx][ny]) == 1) || (b[x][y] == b[nx][ny]))//隣り合っているブロックの絶対値が1か同じなら... { //座標を更新 x = nx; y = ny; //マップ更新 _b[x][y] = '1'; //cout << ">>>NEXT:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl; //さらにその次に行く solve(x, y); //ここに戻ってくるのは行けたけどその先で失敗したとき //各種座標をもとに戻しておく _b[x][y] = '0'; x -= dir[dir_index].dx; y -= dir[dir_index].dy; //cout << "<<<BACK:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl; } break; case 4: case 5: case 6: case 7: if (b[x][y] == b[nx][ny])//2つ先のブロックの高さが同じなら... { //間のブロックの座標を算出 int cx, cy; cx = (x > nx) ? (x - 1) : ((x < nx) ? (x + 1) : x); cy = (y > ny) ? (y - 1) : ((y < ny) ? (y + 1) : y); //間のブロックが低いなら... if (b[x][y] > b[cx][cy]) { //座標を更新 x = nx; y = ny; //マップ更新 _b[x][y] = '1'; //cout << ">>>NEXT:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl; //さらにその次に行く solve(x, y); //ここに戻ってくるのは行けたけどその先で失敗したとき //各種座標をもとに戻しておく _b[x][y] = '0'; x -= dir[dir_index].dx; y -= dir[dir_index].dy; //cout << "<<<BACK:" << "x=" << x << ",y=" << y << ",dir_index=" << dir_index << endl; } } break; } } //枠外だった、または、枠内だけどその先に行けない dir_index++; //方向を変えてみる } while (dir_index < 8); //行ける候補がなくなったら終了 return; } int main() { cin >> H; cin >> W; cin >> sx; cin >> sy; cin >> gx; cin >> gy; for (int x = 1; x <= H; x++) { for (int y = 1; y <= W; y++) { cin >> b[x][y]; } } //_printM(); _b[gx][gy] = '1'; solve(gx, gy); cout << ((ans == 1) ? "YES" : "NO") << endl; //getchar(); return 0; }