如果不相交很好求，就是work函数动态规划就行了，可是相交，最多三个交点，也就是在两个人的路中有一个交点，把这种情况给删除掉，就是(1,2)走到了(N,M-1)和(2,1)走到了(N-1,M)的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
int N,M;
ll mod = 1000000007;
char s[3100][3100];
ll f[2][3100][3100];
void work(int k,int x,int y){
if (s[x][y] == '.') f[k][x][y] = 1;
for (int i = x; i <= N; i++)
for (int j = y; j <= M; j++)
if (s[i][j] == '.' && (i!=x || j!=y)){
f[k][i][j] = (f[k][i-1][j] + f[k][i][j-1]) % mod;
}
}
int main(){
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; i++)
scanf("%s", s[i] + 1);
work(0,1,2);work(1,2,1);
ll ans = ( f[0][N-1][M]*f[1][N][M-1]%mod -
f[0][N][M-1]*f[1][N-1][M]%mod + mod ) % mod;
cout << ans << endl;
return 0;
}
|