从一个点开始，如果始终只往右边和下边走，则如果能到达右下角距离必定是最小的，
且无论走那条路线距离都是一样的。
代码如下：
#include
#include
#include
using namespace std; char str[100]; int G[1000][1000]; int dp[1000][1000]; int n,m; void input() { gets(str); sscanf(str,"%d %d",&n,&m); memset(G,0,sizeof(G)); for(int ii=1;ii<=n;ii++) { gets(str); int len=strlen(str); int temp=0,i; for(i=0;i
='0'&&str[i]<='9') temp=temp*10+str[i]-'0'; else break; } int x=temp; temp=0; for(int j=i+1;j<=len;j++) { if(str[j]>='0'&&str[j]<='9') { temp=temp*10+str[j]-'0'; } else if(str[i]==' '||j==len) { G[x][temp]=1; temp=0; } } } } int main() { int t; gets(str); sscanf(str,"%d",&t); while(t--) { gets(str); input(); memset(dp,0,sizeof(dp)); dp[1][1]=1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(G[i][j]==1) dp[i][j]=0; else dp[i][j]+=dp[i-1][j]+dp[i][j-1]; } printf("%d\n",dp[n][m]); if(t) printf("\n"); } return 0; }