Pascal's Travels
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1331 Accepted Submission(s): 591
Problem Description
An n x n game board is populated with integers, one nonnegative integer per square. The goal is to travel along any legitimate path from the upper left corner to the lower right corner of the board. The integer in any one square dictates how large a step away from that location must be. If the step size would advance travel off the game board, then a step in that particular direction is forbidden. All steps must be either to the right or toward the bottom. Note that a 0 is a dead end which prevents any further progress.
Consider the 4 x 4 board shown in Figure 1, where the solid circle identifies the start position and the dashed circle identifies the target. Figure 2 shows the three paths from the start to the target, with the irrelevant numbers in each removed.
Input
The input contains data for one to thirty boards, followed by a final line containing only the integer -1. The data for a board starts with a line containing a single positive integer n, 4 <= n <= 34, which is the number of rows in this board. This is followed by n rows of data. Each row contains n single digits, 0-9, with no spaces between them.
Output
The output consists of one line for each board, containing a single integer, which is the number of paths from the upper left corner to the lower right corner. There will be fewer than 2^63 paths for any board.
Sample Input
4
2331
1213
1231
3110
4
3332
1213
1232
2120
5
11101
01111
11111
11101
11101
-1
Sample Output
3
0
7
HintHint
Brute force methods examining every path will likely exceed the allotted time limit.
64-bit integer values are available as "__int64" values using the Visual C/C++ or "long long" values
using GNU C/C++ or "int64" values using Free Pascal compilers.
#include <iostream>
#include <cstdio>
using namespace std;
__int64 map[44][44],dp[44][44],n; //dp是記錄路徑數量的
__int64 DP(__int64 x,__int64 y)
{
int i;
if(x==n-1&&y==n-1)return 1; //找到終點就算一條路，就返回1
if(map[x][y]==0||dp[x][y])return dp[x][y]; //map肯定不能為0撒，這還要意思問我為什麼？為0就不能動看，還有DP不為0就是已經確定數量了
if(x+map[x][y]<n) //題目說了只能走直線，這樣方便多了，這樣就是要用兩if來分別橫著和豎著走了
dp[x][y]+=DP(x+map[x][y],y); //當前點的dp要加上走到的那一點的dp，就把DP看成求出裡面坐標的dp值的函數咯
if(y+map[x][y]<n)
dp[x][y]+=DP(x,y+map[x][y]);
return dp[x][y]; //結束完之後返回查找完成的當前點
}
int main (void)
{
__int64 i,j,k,l;
char c;
while(~scanf("%I64d%*c",&n)&&n!=-1)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
scanf("%c",&c),map[i][j]=c-48,dp[i][j]=0;
getchar();
}
printf("%I64d\n",DP(0,0)); //是從(.,.)開始走到，所以從就從這點開始走，就把DP當作返回當前點的路徑數的函數咯
}
return 0;
}
這個和上面寫的那個博客幾乎是一樣的，唉～～這原理你去看那個OK？我可不會悠著悠著來告訴你DP這個函數不能看表面，要知道它是執行到找到目標或者判斷找不到目標的那個遞歸層開始計算的，沒計算好一個，就像上一層返回這一層計算的結果，好好看看吧，這個需要點耐心才能消化的，自己腦子轉一轉就會明白了，擦，還是不懂啊？像找罵是不？這都已經灰常明白了呢，至少我要是第一次看的話會很快就找到的呢- -!親～不懂的話我倒是要鄙視再鼻屎砸你了，別說我暴力，其實我很溫柔!
分享到：
