結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2019-09-10 19:50:58 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 17,263 bytes |
コンパイル時間 | 1,751 ms |
コンパイル使用メモリ | 183,424 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-02 16:19:08 |
合計ジャッジ時間 | 2,612 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
ソースコード
#ifndef _GLIBCXX_NO_ASSERT#include <cassert>#endif#include <cctype>#include <cerrno>#include <cfloat>#include <ciso646>#include <climits>#include <clocale>#include <cmath>#include <csetjmp>#include <csignal>#include <cstdarg>#include <cstddef>#include <cstdio>#include <cstdlib>#include <cstring>#include <ctime>#if __cplusplus >= 201103L#include <ccomplex>#include <cfenv>#include <cinttypes>#include <cstdalign>#include <cstdbool>#include <cstdint>#include <ctgmath>#include <cwchar>#include <cwctype>#endif#include <algorithm>#include <bitset>#include <complex>#include <deque>#include <exception>#include <fstream>#include <functional>#include <iomanip>#include <ios>#include <iosfwd>#include <iostream>#include <istream>#include <iterator>#include <limits>#include <list>#include <locale>#include <map>#include <memory>#include <new>#include <numeric>#include <ostream>#include <queue>#include <set>#include <sstream>#include <stack>#include <stdexcept>#include <streambuf>#include <string>#include <typeinfo>#include <utility>#include <valarray>#include <vector>#if __cplusplus >= 201103L#include <array>#include <atomic>#include <chrono>#include <condition_variable>#include <forward_list>#include <future>#include <initializer_list>#include <mutex>#include <random>#include <ratio>#include <regex>#include <scoped_allocator>#include <system_error>#include <thread>#include <tuple>#include <typeindex>#include <type_traits>#include <unordered_map>#include <unordered_set>#endifusing namespace std;using i32 = int;using i64 = long long;using vi32 = vector<i32>;using vi64 = vector<i64>;using vvi32 = vector<vi32>;using vvi64 = vector<vi64>;using pii32 = pair<i32,i32>;using pii64 = pair<i64,i64>;#define ALL(obj) (obj).begin(),(obj).end()#define bit(n) (1LL<<(n))#define cauto const auto&#define CLR(ar,val) memset(ar, val, sizeof(ar))#define FOR(i,a,b) for(i32 i=(a); i<(i32)(b); i++)#define PRINT(n) cout << (n) <<"\n";#define RALL(obj) ((obj).rbegin(),(obj).rend())#define REP(i,n) FOR(i,0,n)#define SZ(obj) ((i32)(obj).size())#define UNIQUE(v) (v).erase( unique(ALL(v)),v.end() );#define mp make_pair#define pb push_backstatic const double PI = 3.1415926535897932;static const double E = 2.7182818284590452;static const double EPS = 1e-14;static const int INF = 0x3F3F3F3F;static const i64 INFLL = 1e18;static const i64 MOD = (i64) 1e9 + 7;int dy[4] = {1, 0, -1, 0};int dx[4] = {0, 1, 0, -1};/***最大値、最小値を更新する関数***/template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }//拡張ユークリッドの互除法/***x, y にgcd(a, b) = a * x + b * yを満たすx, yを代入して最大公約数が返される***/template<typename T>T extgcd(T a, T b, T &x, T &y) {T d = a;if(b != 0) {d = extgcd(b, a % b, y, x);y -= (a / b) * x;} else {x = 1;y = 0;}return d;}//進数変換/***10進数xをb進数に変換する***/template<typename T>vector<T> convert_base(T x, T b) {vector<T> ret;T t = 1, k = abs(b);while (x) {ret.emplace_back((x * t) % k);if (ret.back() < 0) ret.back() += k;x -= ret.back() * t;x /= k;t *= b / k;}if (ret.empty()) ret.emplace_back(0);reverse(all(ret));return ret;}//ポップカウント/***32bit整数において2進数表示したときの1の数を返してくれる関数***/i32 popCount(i32 data){data = (data & 0x55555555)+ ((data & 0xAAAAAAAA) >> 1);data = (data & 0x33333333)+ ((data & 0xCCCCCCCC) >> 2);data = (data & 0x0F0F0F0F)+ ((data & 0xF0F0F0F0) >> 4);data = (data & 0x00FF00FF)+ ((data & 0xFF00FF00) >> 8);data = (data & 0x0000FFFF)+ ((data & 0xFFFF0000) >> 16);return data;}/***unsigned intを渡すとbit reverseしてくれる関数***/unsigned int bitReverse(unsigned int data){data = ((data & 0x55555555) << 1)| ((data & 0xAA555555) >> 1);data = ((data & 0x33333333) << 2)| ((data & 0xCCCCCCCC) >> 2);data = ((data & 0x0F0F0F0F) << 4)| ((data & 0xF0F0F0F0) >> 4);data = ((data & 0x00FF00FF) << 8)| ((data & 0xFF00FF00) >> 8);data = (data << 16) | (data >> 16);return data;}/***オイラーのφ関数***/i64 euler_phi(i64 n){i64 ret = n;for (i64 i = 2; i * i <= n; i++) {if (n % i == 0) {ret -= ret / i;while (n % i == 0) n /= i;}}if (n > 1) ret -= ret / n;return ret;}/***オイラーのφ関数の表***/vi32 euler_phi_table(i32 n) {vi32 euler(n + 1);for(i32 i = 0; i <= n; i++) {euler[i] = i;}for(i32 i = 2; i <= n; i++) {if(euler[i] == i) {for(i32 j = i; j <= n; j += i) {euler[j] = euler[j] / i * (i - 1);}}}return euler;}/***べき乗(x ^ n)をmodで割ったあまりを計算してくれる関数***/i64 power(i64 x, i64 n, i64 mod) {i64 ret = 1;while (n > 0) {if (n & 1) (ret *= x) %= mod;(x *= x) %= mod;n >>= 1;}return ret;}/***long long型整数を入れると約数を配列にして返してくれる関数***/vi64 divisor(i64 n) {vi64 ret;for(i64 i = 1; i * i <= n; i++) {if(n % i == 0) {ret.push_back(i);if(i * i != n) ret.push_back(n / i);}}sort(ALL(ret));return (ret);}/***long long型整数を入れると素数ならtrue合成数ならfalseを返してくれる関数***/bool is_prime(i64 x) {for(i64 i = 2; i * i <= x; i++) {if(x % i == 0) return false;}return true;}vector<bool> sieve_of_eratosthenes(i32 n) {vector<bool> primes(n+1, true);primes[0] = primes[1] = false;for (i32 i = 2; i*(i64)i <= n; ++i)if (primes[i])for (i32 k = i+i; k <= n; k += i)primes[k] = false;return primes;}/***配列vと区間kを与えるとv[0] - v[k]v[1] - v[k+1]v[2] - v[k+2]の区間ごとの最小値を配列に入れて返してくれる関数***/template<typename T>vector<T> slide_min(const vector<T>& v, i32 k) {deque<i32> deq;vector<T> ret;for (i32 i = 0; i < SZ(v); i++) {while(!deq.empty() && v[deq.back()] >= v[i]) {deq.pop_back();}deq.push_back(i);if(i-k+1 >= 0) {ret.emplace_back(v[deq.front()]);if(deq.front() == i - k + 1) deq.pop_front();}}return ret;}/***a, b, pに対し a ^ x === b (mod p)を満たす非負整数 xを求める関数***/i64 mod_log(i64 a, i64 b, i64 p) {i64 ok = p, ng = -1;while(ok - ng > 1) {auto mid = (ok + ng) / 2;if (mid * mid >= p) ok = mid;else ng = mid;}unordered_map<i64, i64> baby;baby.reserve(ok);i64 factor = 1;for (i64 i = 0, e = b; i < ok; i++) {baby[e] = i;(factor *= a) %= p;(e *= a) %= p;}for (i64 i = 1, e = factor; i <= ok; i++) {auto it = baby.find(e);if (it != baby.end()) return i * ok - it -> second;(e *= factor) %= p;}return -1;}// 最大公約数uint32_t euclidean_gcd(uint32_t a, uint32_t b) {while(a^=b^=a^=b%=a);return b;}// 最小公倍数uint32_t euclidean_lcm(uint32_t a, uint32_t b) {return a * b / euclidean_gcd(a, b);}// カタラン数unsigned long int catalan[200500];unsigned long int catalanDP(unsigned int n) {catalan[0] = catalan[1] = 1;for (unsigned int i = 2; i <= n; i++) {catalan[i] = 0;for (unsigned int j = 0; j < i; j++)catalan[i] += catalan[j] * catalan[i - j - 1];}return catalan[n];}i32 qp(i32 a, i64 b) {i32 ans = 1;do {if (b&1) ans = 1ll * ans * a % MOD;a = 1ll * a * a % MOD;} while (b >>= 1);return ans;}i32 qp(i32 a, i64 b, i32 mo) {i32 ans = 1;do {if (b&1) ans = 1ll * ans * a % mo;a = 1ll * a * a % mo;} while (b>>=1);return ans;}// NTTnamespace NumberTheoreticTransform{constexpr i64 NTT_PRIMES[][2] = {{1224736769, 3}, // 2^24 * 73 + 1,{1053818881, 7}, // 2^20 * 3 * 5 * 67 + 1{1051721729, 6}, // 2^20 * 17 * 59 + 1{1045430273, 3}, // 2^20 * 997 + 1{1012924417, 5}, // 2^21 * 3 * 7 * 23 + 1{1007681537, 3}, // 2^20 * 31^2 + 1{1004535809, 3}, // 2^21 * 479 + 1{998244353, 3}, // 2^23 * 7 * 17 + 1{985661441, 3}, // 2^22 * 5 * 47 + 1{976224257, 3}, // 2^20 * 7^2 * 19 + 1{975175681, 17}, // 2^21 * 3 * 5 * 31 + 1{962592769, 7}, // 2^21 * 3^3 * 17 + 1{950009857, 7}, // 2^21 * 4 * 151 + 1{943718401, 7}, // 2^22 * 3^2 * 5^2 + 1{935329793, 3}, // 2^22 * 223 + 1{924844033, 5}, // 2^21 * 3^2 * 7^2 + 1{469762049, 3}, // 2^26 * 7 + 1{167772161, 3}, // 2^25 * 5 + 1};i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) {i64 d;return b == 0 ? (x = 1, y = 0, a) : (d = extgcd(b, a % b, y, x), y -= a / b * x, d);}i64 modinv(i64 a, i64 mod) {i64 x, y;extgcd(a, mod, x, y);x %= mod;return x < 0 ? x + mod : x;}i64 modpow(i64 a, i64 b, i64 mod) {i64 r = 1;a %= mod;while(b) {if (b & 1) r = r * a % mod;a = a * a % mod;b >>= 1;}return r;}template <i64 mod, i64 primitive>struct Core {Core() { }using uint = uint_fast32_t;int MAX_H;vi64 zetaList, zetaInvList;explicit Core(int MAX_H) : MAX_H(MAX_H), zetaList(MAX_H), zetaInvList(MAX_H) {assert((mod & ((1 << MAX_H) - 1)) == 1);zetaList.back() = modpow(primitive, (mod - 1) / (1 << MAX_H), mod);zetaInvList.back() = modinv(zetaList.back(), mod);for (int ih = MAX_H - 2; ih >= 0; --ih) {zetaList[ih] = zetaList[ih + 1] * zetaList[ih + 1] % mod;zetaInvList[ih] = zetaInvList[ih + 1] * zetaInvList[ih + 1] % mod;}}void fft(vi64 &a, uint n, uint h, bool inv) const {static vi64 tmp;tmp.resize(n);uint mask = n - 1;for (uint i = n >> 1, ih = h - 1; i >= 1; i >>= 1, --ih) {i64 zeta = inv ? zetaInvList[h - 1 - ih] : zetaList[h - 1 - ih];i64 powZeta = 1;for (uint j = 0; j < n; j += i) {for (uint k = 0; k < i; ++k) {tmp[j + k] = (a[((j << 1) & mask) + k] + powZeta * a[(((j << 1) + i) & mask) + k]) % mod;}powZeta = powZeta * zeta % mod;}swap(a, tmp);}if (inv) {i64 invN = modinv(n, mod);for (uint i = 0; i < n; ++i) a[i] = a[i] * invN % mod;}}vi64 conv(const vi64 &a, const vi64 &b) const {assert(a.size() + b.size() - 1 <= (1 << MAX_H));if (a.size() == 0) return {};if (b.size() == 0) return {};return _conv(a, b);}vi64 _conv(vi64 a, vi64 b) const {uint deg = a.size() + b.size() - 1;uint h = 0, n = 1;while(n < deg) n <<= 1, ++h;a.resize(n), b.resize(n);return _convStrict(a, b, n, h);}vi64 _convStrict(vi64 a, vi64 b, uint n, uint h) const {fft(a, n, h, 0), fft(b, n, h, 0);for(uint i = 0; i < n; ++i) a[i] = a[i] * b[i] % mod;fft(a, n, h, 1);return a;}};template<int I>void conv_for(int MAX_H, int n, int h,const vi64 &a,const vi64 &b,vi64 &mods,vi64 &coeffs,vvi64 &constants) {static const Core<NTT_PRIMES[I][0], NTT_PRIMES[I][1]> ntt(MAX_H);auto c = ntt._convStrict(a, b, n, h);mods[I] = NTT_PRIMES[I][0];if(I >= 1) {conv_for<I - 1>(MAX_H, n, h, a, b, mods, coeffs, constants);}for(size_t i = 0; i < c.size(); ++i) {i64 v = (c[i] - constants[I][i]) * modinv(coeffs[I], mods[I]) % mods[I];if(v < 0) v += mods[i];for(size_t j = I + 1; j < mods.size(); ++j) {constants[j][i] = (constants[j][i] + coeffs[j] * v) % mods[j];}}for(size_t j = I + 1; j < mods.size(); ++j) {coeffs[j] = (coeffs[j] * mods[I]) % mods[j];}}template <>void conv_for< -1 >(int, int, int, const vector< i64 > &, const vector< i64 > &,vector< i64 > &, vector< i64 > &,vector< vector< i64 > > &) { }template<int USE>vi64 conv( int MAX_H,vi64 a,vi64 b,i64 mod) {static_assert(USE >= 1, "USE must be positive");static_assert(USE <= sizeof(NTT_PRIMES) / sizeof(*NTT_PRIMES), "USE is too big");int deg = a.size() + b.size() - 1;int n = 1, h = 0;while(n < deg) n <<= 1, ++h;a.resize(n), b.resize(n);vi64 coeffs(USE + 1, 1);vvi64 constants(USE + 1, vi64(n, 0));vi64 mods(USE + 1, mod);conv_for<USE-1>(MAX_H, n, h, a, b, mods, coeffs, constants);return constants.back();}}//namespace NumberTheoreticTransform// BITtemplate<typename T>struct BinaryIndexedTree {vector<T> data;BinaryIndexedTree(int sz) {data.assign(++sz, 0);}T sum(int k) {T ret = 0;for(++k; k > 0; k -= k & -k) ret += data[k];return ret;}void add(int k, T x) {for(++k; k < data.size(); k += k & -k) data[k] += x;}};// セグ木template<typename Monoid>struct SegmentTree {using F = function<Monoid(Monoid, Monoid)>;int sz;vector<Monoid> seg;const F f;const Monoid M1;// n: 数列の数// f: 求めたい関数(例えば最小値など)をラムダ式などで渡す// M1: 初期値SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {sz = 1;while(sz < n) sz <<= 1;seg.assign(2 * sz, M1);}void set(int k, const Monoid &x) {seg[k+sz] = x;}void build() {for (int k = sz - 1; k > 0; k--) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}// xをkに更新するvoid update(int k, const Monoid &x) {k += sz;seg[k] = x;while(k >>= 1) {seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);}}// 第二引数の関数を適用するMonoid query(int a, int b) {Monoid L = M1, R = M1;for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {if(a & 1) L = f(L, seg[a++]);if(b & 1) R = f(seg[--b], R);}return f(L, R);}Monoid operator[](const int &k) const {return seg[k + sz];}};void Main();int main() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << fixed << setprecision(15);Main();return 0;}void Main(){//------------------------------------int h, w, sx, sy, gx, gy;cin >> h >> w >> sy >> sx >> gy >> gx;sx--;sy--;gx--;gy--;string b[55];bool used[55][55];REP(i, h) cin >> b[i];REP(i, 55) REP(j, 55) {used[i][j] = false;}queue<pii32> q;q.push(mp(sy, sx));used[sy][sx] = true;while (!q.empty()) {auto n = q.front(); q.pop();if (n.first == gy && n.second == gx) break;int hh = b[n.first][n.second] - '0';REP(i,4) {int ny = n.first + dy[i], nx = n.second + dx[i];if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;if (used[ny][nx]) continue;int nh = b[ny][nx] - '0';if (abs(nh - hh) <= 1) {used[ny][nx] = true;q.push(mp(ny,nx));}}REP(i,4) {int ny = n.first + 2 * dy[i], nx = n.second + 2 * dx[i];if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue;if (used[ny][nx]) continue;int nh = b[ny][nx] - '0';int ah = b[(ny + n.first) / 2][(nx + n.second) / 2] - '0';if (hh - ah > 0 && nh == hh) {used[ny][nx] = true;q.push(mp(ny,nx));}}}if (used[gy][gx]) cout << "YES" << endl;else cout << "NO" << endl;//------------------------------------}