結果

問題 No.424 立体迷路
コンテスト
ユーザー gigime
提出日時 2016-09-22 22:51:34
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,342 bytes
コンパイル時間 1,552 ms
コンパイル使用メモリ 167,584 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 07:03:03
合計ジャッジ時間 1,866 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (l);i < (r);i++)
#define ALL(x) (x).begin(),(x).end()
template<typename T> void chmax(T& a,const T& b){if(a < b) a = b;}
template<typename T> void chmin(T& a,const T& b){if(b < a) a = b;}
typedef long long ll;

int H,W;
pair<int,int> S,G;
bool vis [50] [50];
const int dx [] = {0,1,0,-1};
const int dy [] = {-1,0,1,0};

bool in_range(int y,int x)
{
	return y >= 0 && y < H && x >= 0 && x < W;
}

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

	cin >> H >> W;
	vector<string> board(H);
	cin >> S.first >> S.second >> G.first >> G.second;
	S.first--,S.second--,G.first--,G.second--;
	FOR(i,0,H){
		cin >> board [i];
	}

	queue< pair<int,int> > q;
	q.push(S);

	while(q.empty() == false){
		int y = q.front().first,x = q.front().second;
		q.pop();

		if(vis [y] [x]) continue;
		vis [y] [x] = true;
		if(make_pair(y,x) == G){
			cout << "YES" << endl;
			return 0;
		}

		FOR(i,0,4){
			int yy = y + dy [i],xx = x + dx [i];
			if(in_range(yy,xx) && abs(board [y] [x] - board [yy] [xx]) <= 1){
				q.push(make_pair(yy,xx));
			}
			if(in_range(yy + dy [i],xx + dx [i]) && board [yy] [xx] < board [y] [x] && board [y] [x] == board [yy + dy [i]] [xx + dx [i]]){
				q.push(make_pair(yy + dy [i],xx + dx [i]));
			}
		}
	}

	cout << "NO" << endl;

	return 0;
}
0