結果

問題 No.424 立体迷路
ユーザー btkbtk
提出日時 2016-09-22 08:53:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,405 bytes
コンパイル時間 1,787 ms
コンパイル使用メモリ 181,268 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-05 06:57:46
合計ジャッジ時間 2,626 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}init;
const int dir[]={0,1,0,-1,0};

vector<string> wrap(vector<string> s,char w){
    int r=s.size();
    int c=s[0].size();
    vector<string> res(r+2,string(c+2,w));
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            res[i+1][j+1]=s[i][j];
    return res;
}
int main(){
    int R,C,sr,sc,gr,gc;
    cin>>R>>C>>sr>>sc>>gr>>gc;
    vector<string> s(R);
    for(auto &it:s)cin>>it;
    sr++;sc++;
    gr++;gc++;
    s=wrap(wrap(s,(char)('9'+2)),(char)('9'+2));
    R=s.size();C=s[0].size();
    vector<vector<bool>> used(R,vector<bool>(C,false));
    queue<int> Qr,Qc;
    Qr.push(sr);Qc.push(sc);
    used[sr][sc]=true;
    while(Qr.size()){
        int r=Qr.front();Qr.pop();
        int c=Qc.front();Qc.pop();
        for(int i=0;i<4;i++){
            int nr=r+dir[i];
            int nc=c+dir[i+1];
            if(abs(0+s[r][c]-s[nr][nc])<=1&&used[nr][nc]==false){
                Qr.push(nr);Qc.push(nc);
                used[nr][nc]=true;
            }
            int mr=nr+dir[i];
            int mc=nc+dir[i+1];
            if(s[r][c]==s[mr][mc]&&s[nr][nc]<s[r][c]&&used[mr][mc]==false){
                Qr.push(mr);Qc.push(mc);
                used[mr][mc]=true;
            }
        }

    }
    if(used[gr][gc])cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}
0