結果

問題 No.424 立体迷路
ユーザー daleksprinterdaleksprinter
提出日時 2018-09-13 22:20:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,818 bytes
コンパイル時間 1,577 ms
コンパイル使用メモリ 167,084 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 07:16:57
合計ジャッジ時間 2,260 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,a,b) for(int i=a;i<b;i++)
#define int long long
const int inf = 100100100100100;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int dx2[4] = {2,0,-2,0};
int dy2[4] = {0,2,0,-2};

int arr[50][50];
int h, w, sx, sy, gx, gy;
int visited[50][50];

int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

bool dfs(int x, int y){
    if(x == gy && y == gx) return true;

    if(visited[y][x] == 1){
        return false;
    }else{
        visited[y][x] = 1;
    }

    rep(i,0,4){
        int tx = x + dx[i]; 
        int ty = y + dy[i];


        if(-1 < tx && tx < w && -1 < ty && ty < h && -2 < arr[ty][tx]-arr[y][x] && arr[ty][tx] - arr[y][x] < 2){
            if(dfs(tx,ty)) return true;
        }
    }

    rep(i,0,4){
        int tx = x + dx2[i];
        int ty = y + dy2[i];
        int mx = x + dx[i]; 
        int my = y + dy[i];

        if(-1 < tx && tx < w && -1 < ty && ty < h && 
            -1 < mx && mx < w && -1 < my && my < h && 
                arr[ty][tx] == arr[y][x] && arr[y][x] > arr[my][mx]){
            if(dfs(tx,ty)) return true;
        }
    }

    return false;

}

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    cin >> h >> w >> sx >> sy >> gx >> gy;
    sx--; sy--; gx--; gy--;

    rep(i,0,h){
        rep(j,0,w){
            char t;
            cin >> t;
            arr[i][j] = ctoi(t);
            visited[i][j] = 0;
        }
    }


    if(dfs(sy,sx)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

}
0