結果

問題 No.424 立体迷路
ユーザー moyashi_senpaimoyashi_senpai
提出日時 2016-09-22 23:12:35
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 5 ms / 2,000 ms
コード長 1,837 bytes
コンパイル時間 781 ms
コンパイル使用メモリ 100,656 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-09-18 16:50:28
合計ジャッジ時間 1,814 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,504 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 2 ms
4,380 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 AC 1 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 5 ms
4,376 KB
testcase_25 AC 4 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <bitset>
#include <stack>
#include <cstdlib>
#include <unordered_map>
#define REP(i,n) for(int i = 0; n > i; i++)
#define MOD 1000000007
#define Range(x,a,b) ((a) <= (x) && (x) <= (b))
#define POWT(x) ((x)*(x))
using namespace std;
typedef vector<int> Ivec;
typedef pair<int, int> pii;
typedef long long int ll;

const pii four_Dir[4] = { //四方向
	{ 0 ,1 },
	{ -1 ,0 },{ 1 ,0 },
	{ 0 ,-1 }
};

int main() {
	int h, w;
	pii s, g;
	scanf("%d %d %d %d %d %d", &h, &w, &s.second, &s.first, &g.second, &g.first);
	s.first--;
	s.second--;
	g.first--;
	g.second--;
	vector<vector<int>> m(w, vector<int>(h));
	REP(i, h) {
		scanf("%*c");
		REP(j, w) {
			char c;
			scanf("%c", &c);
			m[j][i] = c - '0';
		}
	}

	queue<pii> que;
	map<pii,bool> al;
	que.push(s);
	while (que.size()) {
		auto cur = que.front();
		que.pop();
		if (cur == g) {
			printf("YES\n");
			return 0;
		}
		if (al[cur]) continue;
		al[cur] = true;

		REP(i, 4) {
			pii next = {cur.first + four_Dir[i].first, cur.second + four_Dir[i].second};
			if (!al[next] && Range(next.first, 0, w-1) && Range(next.second, 0, h-1)) {
				if (abs(m[cur.first][cur.second] - m[next.first][next.second]) <= 1) {
					que.push(next);
				}
			}
			next = { next.first + four_Dir[i].first, next.second + four_Dir[i].second };
			if (!al[next] && Range(next.first, 0, w-1) && Range(next.second, 0, h-1)) {
				if (m[cur.first][cur.second] > m[next.first - four_Dir[i].first][next.second - four_Dir[i].second] && m[cur.first][cur.second] == m[next.first][next.second]) {
					que.push(next);
				}
			}
		}
	}
	printf("NO\n");
	return 0;
}
0