結果
| 問題 | 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>
#endif
using 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_back
static 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;
}
// NTT
namespace 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
// BIT
template<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;
//------------------------------------
}