题目：http://codeforces.com/contest/348/problem/D
如果只走一条路那就直接dp就可以了。
设cal(x1,y1,x2,y2)为(x1,y1)→(x2,y2)的路径数。
cal(1,2,n-1,m)*cal(2,1,n,m-1)把相交的情况也算进去了。
但是对于每一种相交的情况，发现它们都对应一种将两个终点反转的情况。
那么ans=cal(1,2,n-1,m)*cal(2,1,n,m-1)-cal(1,2,n,m-1)*cal(2,1,n-1,m)
#include<cstring> #include<iostream> #include<cstdio> #include<queue> #include<cmath> #include<algorithm> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define low(x) (x&(-x)) #define maxn 3005 #define inf int(1e9) #define mm 1000000007 #define ll long long using namespace std; ll f[maxn][maxn],ans1,ans2,ans3,ans4; int n,m,mp[maxn][maxn]; char s[maxn]; ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } int main(){ n=read(); m=read(); rep(i,1,n){ scanf("%s",s+1); rep(j,1,m) if (s[j]=='#') mp[i][j]=1; } if (mp[1][2]==1||mp[2][1]==1) {puts("0"); return 0;} f[1][2]=1; rep(i,1,n) rep(j,1,m) if (!mp[i][j]) f[i][j]+=(f[i-1][j]+f[i][j-1])%mm; ans1=f[n-1][m]; ans3=f[n][m-1]; clr(f,0); f[2][1]=1; rep(i,1,n) rep(j,1,m) if (!mp[i][j]) f[i][j]+=(f[i-1][j]+f[i][j-1])%mm; ans2=f[n][m-1]; ans4=f[n-1][m]; printf("%lld ",((ans1*ans2-ans3*ans4)%mm+mm)%mm); return 0; }