結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー MM
提出日時 2025-03-21 23:20:07
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,469 ms / 6,000 ms
コード長 1,066 bytes
コンパイル時間 4,874 ms
コンパイル使用メモリ 259,784 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 23:20:27
合計ジャッジ時間 17,386 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include"bits/stdc++.h"
#include"atcoder/all"
using namespace std;
using mint = atcoder::modint998244353;

int main(){
	int H,W;
	cin >> H >> W;
	vector<string> S(H);
	for(int i = 0; i < H; i++) cin >> S[i];
	
	int N = H+W-2;
	vector<vector<mint>> dp(W,vector<mint>(W,0));
	dp[1][0] = 1;
	
	for(int i = 1; i < N; i++){
		vector<vector<mint>> ndp(W,vector<mint>(W,0));
		for(int a = 0; a < W; a++)
			for(int b = 0; b < W; b++){
				int xa = i-a, xb = i-b;
				
				if(xa < 0 || xa >= H || xb < 0 || xb >= H) continue;
				
				if(xa+1 < H && S[xa+1][a] == '.'){
					if(xb+1 < H && S[xb+1][b] == '.' && (i+1 == N || xb+1 != xa+1))
						ndp[a][b] += dp[a][b];
					if(b+1 < W && S[xb][b+1] == '.' && (i+1 == N || xb != xa+1))
						ndp[a][b+1] += dp[a][b];
				}
				
				if(a+1 < W && S[xa][a+1] == '.'){
					if(xb+1 < H && S[xb+1][b] == '.' && (i+1 == N || xb+1 != xa))
						ndp[a+1][b] += dp[a][b];
					if(b+1 < W && S[xb][b+1] == '.' && (i+1 == N || xb != xa))
						ndp[a+1][b+1] += dp[a][b];
				}
			}
		dp = ndp;
	}
	cout << dp[W-1][W-1].val() << endl;
}
0