結果
問題 | No.2928 Gridpath |
ユーザー |
![]() |
提出日時 | 2024-10-12 16:01:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,657 bytes |
コンパイル時間 | 2,961 ms |
コンパイル使用メモリ | 253,992 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-12 16:02:00 |
合計ジャッジ時間 | 3,791 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define REP(i, x, y) for (auto i = (x); i < (y); i++) #define RREP(i, x, y) for (auto i = (y) - 1; (x) <= i; i--) #define ALL(x) (x).begin(), (x).end() #pragma GCC optimize("O3") template<class T> bool inr(const T &l, const T &x, const T &r){return (l<=x && x<r);} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; int Si, Sj, Gi, Gj; cin >> H >> W >> Si >> Sj >> Gi >> Gj; Si--, Sj--, Gi--, Gj--; vector<vector<int>> c(H, vector<int>(W)); int dy[4] = {0,1,0,-1}; int dx[4] = {1,0,-1,0}; int ans = 0; function<void(int, int)> dfs = [&](int i, int j){ // cout << i << " " << j << "\n"; // REP(k, 0, H){ // REP(l, 0, W){ // cout << c[k][l] << " "; // } // cout << "\n"; // } if(i == Gi && j == Gj){ ans++; return; } REP(d, 0, 4){ int ni = i + dy[d]; int nj = j + dx[d]; if(!inr(0, ni, H))continue; if(!inr(0, nj, W))continue; if(c[ni][nj] == 1)continue; vector<array<int, 2>> memo; REP(e, 0, 4){ if(e == d)continue; int mi = i + dy[e]; int mj = j + dx[e]; if(!inr(0, mi, H))continue; if(!inr(0, mj, W))continue; if(c[mi][mj] == 1)continue; memo.push_back({mi, mj}); c[mi][mj] = 1; } c[i][j] = 1; dfs(ni, nj); c[i][j] = 0; REP(e, 0, ssize(memo)){ c[memo[e][0]][memo[e][1]] = 0; } } return; }; dfs(Si, Sj); cout << ans << "\n"; return 0; } /* File : ~/yukicoder/midoriika_3rd/J.cpp Date : 2024/10/12 Time : 15:31:09 */