题目大意
略...
题解
开始两个人一定是一个向右走一个向下走，向右走的人最终会走到(n-1,m),向下走的人一定会走到(n,m-1)。
那么不考虑重复的话总的路径数就是从(1,2)到(n-1,m)的路径数*从(2,1)到(n,m-1)的路径数，这个用 dp 就可以解决，dp 方程是dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ]
其中 dp[i][j]表示从起点到(i,j)的方案数。
考虑两条相交的路径，找到第一个交点，然后让这两个人在这个交点相交后走对方的路径。也就是第一步向下的人走到(n-1,m),另一个人走到(n,m-1)。
对于任何一条相交的路径，我们都可以进行如上转化，所以相交路径的方案数就是从(1,2)到(n,m-1)的路径数*从(2,1)到(n-1,m)的路径数.。同样用 dp 解决。
#include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #define ll long long using namespace std; inline int read() { int sum = 0,p = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') p = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (sum *= 10) += ch - '0'; ch = getchar(); } return sum * p; } const ll mod = 5462617; int n,m; int mp[2009][2009]; ll dp[2009][2009]; ll ans1,ans2,ans3,ans4; int main() { freopen("path.in","r",stdin); freopen("path.out","w",stdout); n = read(),m = read(); for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { scanf("%1d",&mp[i][j]); mp[i][j] ^= 1; } if(mp[2][1] == 0 || mp[1][2] == 0) { puts("0"); return 0; } dp[1][1] = 1; for(int i = 2; i <= n; i++) for(int j = 1; j <= m; j++) { if(mp[i][j]) dp[i][j] = (dp[i - 1][j] +dp[i][j - 1])%mod; } ans1 = dp[n][m - 1]; ans2 = dp[n - 1][m]; memset(dp,0,sizeof(dp)); dp[1][1] = 1; for(int i = 1;i <= n;i++) for(int j = 2;j <= m;j++) { if(mp[i][j]) dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod; } ans3 = dp[n][m - 1]; ans4 = dp[n - 1][m]; printf("%lld",(ans1 * ans4 % mod - ans2 * ans3 % mod + mod)%mod); return 0; }