結果
問題 | No.3071 Double Speedrun |
ユーザー |
|
提出日時 | 2025-03-21 22:14:20 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,090 ms / 6,000 ms |
コード長 | 1,469 bytes |
コンパイル時間 | 6,359 ms |
コンパイル使用メモリ | 332,332 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-21 22:14:35 |
合計ジャッジ時間 | 13,701 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using mint = atcoder::static_modint<998244353>; // using mint = atcoder::static_modint<1000000007>; using ld = long double; using ll = long long; #define mp(a,b) make_pair(a,b) #define rep(i,s,n) for(int i=s; i<(int)n; i++) using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>; const vector<int> dx{1,0,-1,0},dy{0,1,0,-1}; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int h,w;cin >> h >> w; vector<string> s(h);rep(i,0,h)cin >> s[i]; vector<vector<mint>> dp(w,vector<mint>(w)); dp[0][1]=1; for(int k=2; k<h+w-2; k++){ vector<vector<mint>> next_dp(w,vector<mint>(w)); rep(ja,0,w)rep(jb,ja+1,w)if(dp[ja][jb]!=0){ int ia=k-1-ja; int ib=k-1-jb; if(0<=min(ia,ib) && max(ia,ib)<h && 0<=min(ja,jb) && max(ja,jb)<w)rep(p,0,2)rep(q,0,2){ int xa=ia+dx[p],ya=ja+dy[p]; int xb=ib+dx[q],yb=jb+dy[q]; if(xa!=xb && max(xa,xb)<h && max(ya,yb)<w && s[xa][ya]!='#' && s[xb][yb]!='#'){ next_dp[ya][yb]+=dp[ja][jb]; } } } swap(dp,next_dp); // mint sum=0; // rep(i,0,w)rep(j,0,w)sum+=dp[i][j]; // cout << sum.val() << "\n"; } mint ans=0; rep(i,0,w)rep(j,0,w)ans+=dp[i][j]; cout << ans.val(); }