題目意思： 給一張表格，讓你從左上端走到右下端的最短路徑有多少種。其中有些交叉點不能走。 解題思路： 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.2cto.com } if(save[1][1]) printf("0\n"); else printf("%lld\n",dfs(1,1)); if(t) putchar('\n'); } return 0; }
