题目: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=,f=; char ch=getchar();
while (!isdigit(ch)) {if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
int main(){
n=read(); m=read();
rep(i,,n){
scanf("%s",s+);
rep(j,,m) if (s[j]=='#') mp[i][j]=;
}
if (mp[][]==||mp[][]==) {puts(""); return ;}
f[][]=;
rep(i,,n) rep(j,,m) if (!mp[i][j]) f[i][j]+=(f[i-][j]+f[i][j-])%mm;
ans1=f[n-][m]; ans3=f[n][m-];
clr(f,); f[][]=;
rep(i,,n) rep(j,,m) if (!mp[i][j]) f[i][j]+=(f[i-][j]+f[i][j-])%mm;
ans2=f[n][m-]; ans4=f[n-][m];
printf("%lld\n",((ans1*ans2-ans3*ans4)%mm+mm)%mm);
return ;
}

最新文章

  1. jquery函数理解与运用
  2. webapi修改tt模板给字段添加JsonIgnore特性解决转换json循环引用问题
  3. asp.net core 使用EF7 Code First 创建数据库,同时使用命令创建数据库
  4. Can not issue data manipulation statements with executeQuery() 异常处理
  5. 常用 CSS 中文字体 Unicode 编码表
  6. 统一样式的View应该用style修饰
  7. C#_Ajax_分页
  8. mysql的数据导入导出
  9. 通过url给action传中文参数乱码解决方案
  10. DTD验证XML(转)
  11. NetMQ
  12. ios 网络/本地播放器
  13. 使用angular4和asp.net core 2 web api做个练习项目(三)
  14. ruby klb.rb irb
  15. BIOS 中断向量表
  16. 在linux和本地系统之间进行数据传输的简单方法--lrzsz
  17. Java开发岗位面试题归类
  18. 背水一战 Windows 10 (77) - 控件(控件基类): ContentControl, UserControl, Page
  19. ThiNet: A Filter Level Pruning Method for Deep Neural Network Compression笔记
  20. 20170719 Mysql 配置远端Mysql访问,增加表/存储过程

热门文章

  1. java.lang.StringBuilder和java.lang.StringBuffer (JDK1.8)
  2. JAVA Socket编程(一)之UDP通信
  3. bzoj 4012: [HNOI2015]开店
  4. 点击按钮显示隐藏DIV,点击DIV外面隐藏DIV
  5. Logback分别打印info日志和error日志
  6. 记录优雅的pythonic代码
  7. Java数组的创建和初始化
  8. MyBatis单个多个参数传递
  9. Git-分布式版本控制系统(一)
  10. python3之序列化(pickle&amp;json&amp;shelve)