#377966 (C++14) No.424 立体迷路

提出ソース
結果

問題	No.424 立体迷路
ユーザー	佐藤淳平
提出日時	2019-09-10 19:48:38
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	17,276 bytes
コンパイル時間	2,120 ms
コンパイル使用メモリ	191,192 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-02 16:19:17
合計ジャッジ時間	2,906 ms
ジャッジサーバーID （参考情報）	judge4 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

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

raw source code
#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;

const int dy[4] = {1, 0, -1, 0};
const 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;
    //------------------------------------
}
yukicoder

結果

テストケース

ソースコード
