結果

問題 No.2695 Warp Zone
ユーザー taipikataipika
提出日時 2024-03-22 22:20:42
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,827 bytes
コンパイル時間 4,575 ms
コンパイル使用メモリ 247,532 KB
実行使用メモリ 818,280 KB
最終ジャッジ日時 2024-09-30 11:52:03
合計ジャッジ時間 6,181 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
#define all(x) (x).begin(), (x).end()
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    ll s = (ll)v.size();
    for (ll i = 0; i < s; i++) os << (i ? ' ' : ' ') << v[i];
    return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (auto &x : v) is >> x;
    return is;
}
//エラトステネスのふるい
bool IsPrime(ll num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
//    map<pair<ll,ll>,bool> mp;
//    rep(i,m) {
//        mp[make_pair(x[i],y[i])]=true;
//    }
#define rep(i, n) for (ll (i) = 0; (i) < (ll)(n); (i)++)
int main() {
    ll h,w,n;
    cin >> h >> w >> n;
    vector<ll> a(n);
    vector<ll> b(n);
    vector<ll> c(n);
    vector<ll> d(n);
    map<pair<ll,ll>,ll> fmp;
    map<pair<ll,ll>,ll> smp;
    map<pair<ll,ll>,bool> bmp;
    rep(i,n) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        fmp[make_pair(a[i],b[i])]=c[i];
        smp[make_pair(a[i],b[i])]=d[i];
        bmp[make_pair(a[i],b[i])]=true;
    }
    queue<pair<ll,ll>> q;
    vector<vector<ll>> mint(h,vector<ll>(w,1e18));
    mint[0][0]=0;
    q.push(make_pair(1,1));
    while(!q.empty()) {
        ll f=q.front().first;
        ll s=q.front().second;
        q.pop();
        if (f-1>0&&mint[f-2][s-1]==1e18) {
            q.push(make_pair(f-1,s));
            mint[f-2][s-1]=min(mint[f-2][s-1],mint[f-1][s-1]+1);
        }
        if (h-1>=f&&mint[f][s-1]==1e18) {
            q.push(make_pair(f+1,s));
            mint[f][s-1]=min(mint[f][s-1],mint[f-1][s-1]+1);
        }
        if (s-1>0&&mint[f-1][s-2]==1e18) {
            q.push(make_pair(f,s-1));
            mint[f-1][s-2]=min(mint[f-1][s-2],mint[f-1][s-1]+1);
        }
        if (w-1>s&&mint[f-1][s]==1e18) {
            q.push(make_pair(f,s+1));
            mint[f-1][s]=min(mint[f-1][s],mint[f-1][s-1]+1);
        }
        if (bmp[{f-1,s-1}]&&mint[f-1][s]!=1e18) {
        q.push({fmp[{f-1,s-1}],smp[{f-1,s-1}]});
        mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]]=min(mint[fmp[{f-1,s-1}]][smp[{f-1,s-1}]],mint[f-1][s-1]+1);
        }

    }

cout << mint[h-1][w-1] << endl;

}
0