結果

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

ソースコード

diff # 

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


#define MAX 52

int r[MAX][MAX];

int sx;
int sy;
int gx;
int gy;

int h;
int w;

int id[MAX][MAX];
bool use[MAX][MAX];

queue<pair<int,int> > q;
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
bool ok(int a, int b){
	return a >= 0 && b >= 0 && a < h&&b < w;
}
int main(){
	cin >> h >> w;
	cin >> sx >> sy >> gx >> gy;
	sx--;
	sy--;
	gx--;
	gy--;
	int cc = 0;
	for (int i = 0; i < h; i++){
		for (int j = 0; j < w; j++){
			id[i][j] = cc;
		}
	}
	for (int i = 0; i < h; i++){
		string s;
		cin >> s;
		for (int j = 0; j < w; j++){
			r[i][j] = s[j] - '0';
		}
	}
	q.push(make_pair(sx, sy));
	use[sx][sy] = true;
	while (!q.empty()){
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++){
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (ok(xx, yy)){
				if (abs(r[xx][yy] - r[x][y]) <= 1){
					if (use[xx][yy] == false){
						use[xx][yy] = true;
						q.push(make_pair(xx, yy));
					}
				}
				if (r[x][y] > r[xx][yy]){
					int xxx = xx + dx[i];
					int yyy = yy + dy[i];
					if (ok(xxx, yyy)){
						if (r[x][y] == r[xxx][yyy]){
							if (use[xxx][yyy] == false){
								q.push(make_pair(xxx, yyy));
								use[xxx][yyy] = true;
							}
						}
					}
				}
			}
		}
	}
	if (use[gx][gy]){
		puts("YES");
	}
	else{
		puts("NO");
	}
	return 0;
}
0