結果
問題 | No.8063 幅優先探索 |
ユーザー | gyouzasushi |
提出日時 | 2020-04-01 21:52:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,701 bytes |
コンパイル時間 | 1,968 ms |
コンパイル使用メモリ | 181,380 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-06-27 10:36:27 |
合計ジャッジ時間 | 2,384 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | WA | - |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | WA | - |
testcase_06 | AC | 69 ms
8,448 KB |
testcase_07 | AC | 79 ms
8,448 KB |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | AC | 2 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--) #define all(x) (x).begin(), (x).end() #define sz(x) int(x.size()) #define get_unique(x) x.erase(unique(all(x)), x.end()); typedef long long ll; typedef complex<double> Complex; const int INF = 1e9; const ll MOD = 1e9 + 7; const ll LINF = 1e18; template <class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } template <class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } template <class T> vector<T> make_vec(size_t a) { return vector<T>(a); } template <class T, class... Ts> auto make_vec(size_t a, Ts... ts) { return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...)); } vector<int> dy = {0, 1, 0, -1}; vector<int> dx = {1, 0, -1, 0}; int main() { int h, w, sy, sx, gy, gx; cin >> h >> w >> sx >> sy >> gx >> gy; sy--; sx--; gy--; gx--; auto v = make_vec<char>(h, w); rep(i, h) rep(j, w) cin >> v[i][j]; auto d = make_vec<int>(h, w); rep(i, h) rep(j, w) d[i][j] = -1; queue<pair<int, int>> q; d[sy][sx] = 0; q.push({sy, sx}); while (sz(q)) { int y, x; tie(y, x) = q.front(); q.pop(); rep(k, 4) { int ny = y + dy[k], nx = x + dx[k]; if (!(0 <= ny && ny < h && 0 <= nx && nx < w)) continue; if (v[ny][nx] != '.') continue; if (d[ny][nx] != -1) continue; d[ny][nx] = d[y][x] + 1; q.push({ny, nx}); } } cout << d[gy][gx] << endl; }