結果

問題 No.3063 幅優先探索
ユーザー tomatoma
提出日時 2020-04-01 21:53:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,829 bytes
コンパイル時間 1,762 ms
コンパイル使用メモリ 183,980 KB
実行使用メモリ 13,312 KB
最終ジャッジ日時 2024-06-27 10:39:36
合計ジャッジ時間 2,463 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 142 ms
13,312 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T minch(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T maxch(T& l, T r) {
    return l = max(l, r);
}
template<typename T>
void output(const T& val) {
    cout << val << endl;
}
template<typename T>
void output(const vector<T>& vec, const bool newline = false) {
    for (const T& val : vec)cout << val << (newline ? '\n' : ' '); cout << endl;
}
template<typename T>
void output(const vector<vector<T>>& mat) {
    for (const auto& row : mat)output(row);
}
// ============ template finished ============

int main()
{
    int R, C;
    pii s, g;
    cin >> R >> C >> s.first >> s.second >> g.first >> g.second;
    s.first--, s.second--, g.first--, g.second--;
    vector<string> c(R);
    rep(i, R)cin >> c[i];

    Mat d(R, vector<ll>(C, INFL));
    priority_queue<tp3, vector<tp3>, greater<tp3>> pq;
    d[s.first][s.second] = 0;
    pq.push(make_tuple(0, s.first, s.second));
    while (!pq.empty()) {
        int p, h, w;
        tie(p, h, w) = pq.top(); pq.pop();
        rep(dir, 4) {
            int nr = h + dh[dir], nc = w + dw[dir];
            if (!isin(R, C, nr, nc) || c[nr][nc] == '#' || d[nr][nc] <= p + 1)continue;
            d[nr][nc] = p + 1;
            pq.push(make_tuple(p + 1, nr, nc));
        }
    }
    output(d[g.first][g.second]);
    return 0;
}
0