j122 - 11957 - Checkers
題目描述
題目給定一個 n x n 的棋盤，棋盤上包含白子 (W)、黑子 (B) 和空位 (.)。目標是計算白子移動到棋盤最上方一列的所有可能路徑數量。白子只能沿對角線方向移動，即 (x, y) 可以移動到 (x+1, y+1) 或 (x-1, y+1)。如果目標位置有黑子，白子可以跳過它，移動到 (x+2, y+2) 或 (x-2, y+2)。答案需要取模 1000007。
解題思路
這題可以使用動態規劃來解決。dp[i][j] 表示從位置 (i, j) 到最上方一列的可能路徑數量。從棋盤的底部往上遍歷，如果當前位置是白子，則計算從該位置到上方兩格的可能路徑數量，並將其加到上方兩格的 dp 值中。需要考慮跳過黑子的情況。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(n^2)
程式碼
#include <bits/stdc++.h>
using namespace std;
long long n,t,dp[105][105],ans,mod=1000007;
char c;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
for(int ca=1;ca<=t;++ca){
ans=0;
memset(dp,0,sizeof(dp));
cin >> n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j){
cin >> c;
if(c=='W')
dp[i][j]=1;
else if(c=='B')
dp[i][j]=-1;
}
for(int i=n;i>=1;--i){
for(int j=1;j<=n;++j){
if(dp[i][j]>0){
dp[i][j]%=mod;
if(i==1)
ans+=dp[i][j];
else{
if(dp[i-1][j+1]!=-1)
dp[i-1][j+1]+=dp[i][j];
else if(i>1&&j<n&&dp[i-1][j+1]==-1&&dp[i-2][j+2]!=-1)
dp[i-2][j+2]+=dp[i][j];
if(dp[i-1][j-1]!=-1)
dp[i-1][j-1]+=dp[i][j];
else if(i>1&&j>1&&dp[i-1][j-1]==-1&&dp[i-2][j-2]!=-1)
dp[i-2][j-2]+=dp[i][j];
}
}
}
}
cout << "Case " << ca << ": " << ans%mod << "\n";
}
}