dp uva-825-Walking on the Safe Side
题目意思：
给一张表格，让你从左上端走到右下端的最短路径有多少种。其中有些交叉点不能走。
解题思路：
dp.
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#define eps 1e-6
#define INF (1<<20)
#define PI acos(-1.0)
using namespace std;
//数据的读法注意
long long dp[2200][2200],m,n;
int save[2200][2200];
int dir[2][2]={{0,1},{1,0}}; //只能向下和向下走，因为要求用最少的步子到达
bool issure(int row,int column) //判断是否越界
{
if(row<1||row>m||column<1||column>n)
return false;
return true;
}
long long dfs(int row,int column)
{
if(row==m&&column==n) //到达了最后的位置
return dp[m][n]=1;
if(dp[row][column]) //如果已经走过，直接返回
return dp[row][column];
long long tempans=0;
for(int i=0;i<2;i++) //分两步走
{
int temprow=row+dir[i][0],tempcolumn=column+dir[i][1];
if(issure(temprow,tempcolumn)&&save[temprow][tempcolumn]==0)
tempans+=dfs(temprow,tempcolumn);
}
return dp[row][column]=tempans;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
memset(save,0,sizeof(save));
memset(dp,0,sizeof(dp));
//memset(visit,false,sizeof(visit));
for(int i=1;i<=m;i++)
{
int tempint;
char tempchar[220];
scanf("%d",&tempint);
gets(tempchar);
int len=strlen(tempchar);
int num=0;
for(int j=0;j<len;j++) //一个一个整数的读
{
if(isdigit(tempchar[j]))
num=num*10+tempchar[j]-'0';
else
{
save[i][num]=1;
num=0;
}
}
save[i][num]=1; //注意处理最后一个，不然最后一个没有处理
/*scanf("%d%c",&tempint,&tempchar);
while(tempchar!='\n') //注意这种读入方式如果有多个空格则不行，不严谨
{
scanf("%d%c",&tempint,&tempchar);
save[i][tempint]=1;
}*/ www.zzzyk.com
}
if(save[1][1])
printf("0\n");
else
printf("%lld\n",dfs(1,1));
if(t)
putchar('\n');
}
return 0;
}
补充：软件开发 , C++ ,
