这道题是上学期的上机题，上学期完全看不懂什么意思，其实这个题就是个马拦过河卒的问题，但是我还是没思路。
water师父告诉我用动态规划可以做，无奈我太愚笨，让他讲了一遍才懂。
不过效率比water神用动态规划做的提高了15ms.
仰慕water神用DP做。要注意判断边界。
题目描述
Tom和Alice结婚一段时间了，感情非常好，一天他们相约去旅行，终点在遥远的地方。
地形是非常复杂的，路途是非常曲折的。但我们简化一下是一个矩阵。起点也就是他们家在矩阵的左下角，终点也就是他们要去的遥远的地方在右上角，矩阵行列的交点是他们可以驻足的地方，但是有的却是陷阱，他们是不能从那里通过的。Tom要听Alice的，只会往上或往右走，不往回走，直到终点。
Alice要Tom提前算出从起点到终点一共有多少条路，可Tom不会啊，所以就找到你了，你是编程高手，希望你帮他解决这个问题，不然他们的婚姻就有危机了。
输入
输入数据的第一行是两个正整数H，W(2 < H，W < 20),代表矩阵的高和宽。接下来是一个矩阵，共H行，每行W个元素，用空格隔开，元素取值只有0或1，0表示可以走，1表示是陷阱，数据保证位于起点和终点的元素肯定是0。
输出
输出一个整数，即从起点到终点的路径数。
示例输入
5 5 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0
示例输出
2
View Code
1 #include<stdio.h> 2 int d[100][100]; 3 int a[100][100]; 4 int n,m; 5 int main() 6 { 7 int i,j; 8 scanf("%d%d",&n,&m); 9 for(i=1;i<=n;i++) 10 for(j=1;j<=m;j++) 11 scanf("%d",&a[i][j]); 12 d[n][1]=1; 13 for(i=n;i>=1;i--) 14 for(j=1;j<=m;j++) 15 { 16 if(a[i][j]==1) 17 d[i][j]=0; 18 else if(j==1&&i<n) 19 d[i][j]=d[i+1][j]; 20 else if(i==n&&j>1) 21 d[i][j]=d[i][j-1]; 22 else if(i!=n&&j!=1&&a[i][j]!=1) 23 d[i][j]=d[i][j-1]+d[i+1][j]; 24 } 25 printf("%d\n",d[1][m]); 26 return 0; 27 }