結果
問題 | No.2928 Gridpath |
ユーザー |
|
提出日時 | 2024-10-12 15:52:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 13 ms / 2,000 ms |
コード長 | 1,290 bytes |
コンパイル時間 | 1,945 ms |
コンパイル使用メモリ | 177,620 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 15:52:32 |
合計ジャッジ時間 | 2,284 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; void culc(int &ans, set<pair<int, int>> &st, pair<int, int> now, int h, int w, pair<int, int> g) { vector<pair<int, int>> v; if (now.first != 1) v.push_back({now.first - 1, now.second}); if (now.first != h) v.push_back({now.first + 1, now.second}); if (now.second != 1) v.push_back({now.first, now.second - 1}); if (now.second != w) v.push_back({now.first, now.second + 1}); for (auto p : v) { if (st.count(p) == 1) continue; int cnt = 0; vector<pair<int, int>> dx = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; for (int i = 0; i < 4; i++) { if (st.count({p.first + dx[i].first, p.second + dx[i].second}) == 1) cnt++; } if (cnt > 1) continue; if (p == g) ans++; else { st.insert(p); culc(ans, st, p, h, w, g); st.erase(p); } } } void solve() { int h, w; cin >> h >> w; pair<int, int> s, g; cin >> s.first >> s.second >> g.first >> g.second; int ans = 0; set<pair<int, int>> st; st.insert(s); culc(ans, st, s, h, w, g); cout << ans << endl; } int main() { std::cin.tie(0)->sync_with_stdio(0); cout << setprecision(20); int CNT = 1; for (int i = 0; i < CNT; i++) solve(); }