結果

問題 No.3071 Double Speedrun
コンテスト
ユーザー MM
提出日時 2025-03-21 23:17:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,071 bytes
コンパイル時間 4,442 ms
コンパイル使用メモリ 257,776 KB
実行使用メモリ 516,096 KB
最終ジャッジ日時 2025-03-21 23:17:58
合計ジャッジ時間 18,076 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge7
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 MLE * 9
権限があれば一括ダウンロードができます

ソースコード

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<vector<mint>>> dp(N+1,vector<vector<mint>>(W,vector<mint>(W,0)));
	dp[1][1][0] = 1;
	
	for(int i = 1; i < N; i++)
		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))
						dp[i+1][a][b] += dp[i][a][b];
					if(b+1 < W && S[xb][b+1] == '.' && (i+1 == N || xb != xa+1))
						dp[i+1][a][b+1] += dp[i][a][b];
				}
				
				if(a+1 < W && S[xa][a+1] == '.'){
					if(xb+1 < H && S[xb+1][b] == '.' && (i+1 == N || xb+1 != xa))
						dp[i+1][a+1][b] += dp[i][a][b];
					if(b+1 < W && S[xb][b+1] == '.' && (i+1 == N || xb != xa))
						dp[i+1][a+1][b+1] += dp[i][a][b];
				}
			}
	
	cout << dp[N][W-1][W-1].val() << endl;
}
0