結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0