結果

問題 No.424 立体迷路
コンテスト
ユーザー かに
提出日時 2016-10-02 21:21:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,815 bytes
コンパイル時間 1,936 ms
コンパイル使用メモリ 185,612 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-05 07:11:11
合計ジャッジ時間 2,366 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define _CRT_SECURE_NO_WARNINGS
#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define Pi pair<int,int>
#define IINF 1e9
#define LINF 1e18
#define vi vector<int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 0, 1,0,-1 };
int dy[] = { 1, 0,-1,0 };
int dx2[] = { 0,2,0,-2 };
int dy2[] = { 2,0,-2,0 };

class UnionFind {
public:
	vector< vector<int> > rank;
	vector< vector<pair<int, int> > > p;
	UnionFind() {
		rank.resize(51);
		p.resize(51);
		rep(i, 51) {
			rank[i].resize(51, 0);
			p[i].resize(51, make_pair(0, 0));
		}
		rep(i, 51) {
			rep(j, 51) {
				makeSet(make_pair(i, j));
			}
		}
	}

	void makeSet(pair<int, int> x) {
		p[x.second][x.first] = x;
		rank[x.second][x.first] = 0;
	}

	bool same(pair<int, int> x, pair<int, int> y) {
		return p[x.second][x.first] == p[y.second][y.first];
	}

	void unite(pair<int, int> x, pair<int, int> y) {
		link(findSet(x), findSet(y));
	}

	void link(pair<int, int> x, pair<int, int> y) {
		if (rank[x.second][x.first] > rank[x.second][x.first]) {
			p[x.second][x.first] = x;
		}
		else {
			p[x.second][x.first] = y;
			if (rank[x.second][x.first] == rank[x.second][x.first]) {
				rank[x.second][x.first] += 1;
			}
		}
	}

	pair<int, int> findSet(pair<int, int> x) {
		if (x != p[x.second][x.first]) {
			p[x.second][x.first] = findSet(p[x.second][x.first]);
		}
		return p[x.second][x.first];
	}
};

void solve() {
	int h, w, sx, sy, gx, gy;
	cin >> h >> w >> sx >> sy >> gx >> gy;
	sx--; sy--; gx--; gy--;
	int field[51][51];
	rep(i, h) {
		string s;
		cin >> s;
		rep(j, s.length()) {
			field[i][j] = (s[j] - '0') - 1;
		}
	}
	UnionFind uf;
	stack<pair<int, int> > st;
	pair<int, int> stp = make_pair(sy, sx);
	st.push(stp);
	uf.makeSet(stp);
	while (!st.empty()) {
		pair<int, int> top = st.top(); st.pop();
		if (!uf.same(top, stp) || top == stp) {
			uf.unite(top, stp);
			rep(i, 4) {
				int nx = top.second + dx[i]; int ny = top.first + dy[i];
				if (nx >= 0 && nx < h && ny >= 0 && ny < w) {
					int gap = abs(field[top.second][top.first] - field[nx][ny]);
					if (gap == 1 || gap == 0) {
						st.push(make_pair(ny, nx));
					}
				}
			}
			rep(i, 4) {
				int nx = top.second + dx[i]; int ny = top.first + dy[i];
				int nx2 = top.second + dx2[i]; int ny2 = top.first + dy2[i];
				if (nx2 >= 0 && nx2 < h && ny2 >= 0 && ny2 < w) {
					if (field[top.second][top.first] == field[nx2][ny2] && field[top.second][top.first] > field[nx][ny]) {
						st.push(make_pair(ny2, nx2));
					}
				}
			}
		}
	}
	pair<int, int> gp = make_pair(gy, gx);
	if (uf.same(stp, gp)) {
		P("YES");
	}
	else {
		P("NO");
	}
}

int main() {
	solve();
	return 0;
}
0