點擊打開鏈接

題意：給定一張有壞點的網格圖,求左上角走到右下角的兩條不相交路徑的方案數

思路：

考慮如果只有一條路該怎么做顯然 DP 就行了那么我們定義 Calc ( x 1 , y 1 , x 2 , y 2 ) 為從 ( x 1 , y 1 ) 走到 ( x 2 , y 2 ) 的方案數如果不考慮相交,那么答案就是 Calc (2,1, n , m - 1) * Calc (1, 2, n - 1, m )現在考慮相交后,對于一種相交的方案,我們選擇最后一個相交的點,將兩人從這個點往后的目標反轉一下,這樣可以映射到一條從 (2,1) 走到 ( n - 1, m ) 的路徑和一條從 (1, 2) 走到 ( n , m - 1) 的路徑這樣我們就將原先每種不合法的方案和反轉后的每種方案建立起了映射故答案為 Calc (2,1, n , m - 1) * Calc (1, 2, n - 1, m ) - Calc (2,1, n - 1, m ) * Calc (1, 2, n , m - 1)時間復雜度 O ( nm )

代碼：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int mod = 1000000007;const int maxn = 3e3+10;int n,m;char mp[maxn][maxn];ll dp[maxn][maxn];ll solve(int x,int y, int tx,int ty){	if(mp[x][y] == '#') return 0;	memset(dp,0,sizeof(dp));	dp[x][y] = 1;	for(int i=1; i<=n; i++)		for(int j=1; j<=m; j++){			if(mp[i][j] == '#')				continue;			dp[i][j] += dp[i-1][j]+dp[i][j-1];			dp[i][j] %= mod;		}	return dp[tx][ty];}int main(){	scanf("%d%d",&n,&m);	for(int i=1; i<=n; i++) 		scanf("%s",mp[i]+1);	ll ans = (solve(1,2,n-1,m)*solve(2,1,n,m-1)%mod - solve(1,2,n,m-1)*solve(2,1,n-1,m)%mod + mod) % mod;	cout << ans << endl;}