#118579 (C++11) No.424 立体迷路

• 問題: No.424 立体迷路
• ユーザー: Kmcode1
• 提出日時: 2016-09-22 22:32:32
• 言語: C++11 (gcc 11.4.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

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	1 ms; 5,376 KB
testcase_03	AC	1 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	1 ms; 5,376 KB
testcase_07	AC	1 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	2 ms; 5,376 KB
testcase_10	AC	1 ms; 5,376 KB
testcase_11	AC	1 ms; 5,376 KB
testcase_12	AC	1 ms; 5,376 KB
testcase_13	AC	1 ms; 5,376 KB
testcase_14	AC	1 ms; 5,376 KB
testcase_15	AC	1 ms; 5,376 KB
testcase_16	AC	1 ms; 5,376 KB
testcase_17	AC	1 ms; 5,376 KB
testcase_18	AC	2 ms; 5,376 KB
testcase_19	AC	1 ms; 5,376 KB
testcase_20	AC	2 ms; 5,376 KB
testcase_21	AC	2 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	1 ms; 5,376 KB

ソースコード

#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;
}