HDU 1978 How many ways？ dp 記憶化搜尋

How many ways

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 4095    Accepted Submission(s): 2396

Problem Description 這是一個簡單的生存遊戲，你控制一個機器人從一個棋盤的起始點(1,1)走到棋盤的終點(n,m)。遊戲的規則描述如下：

1.機器人一開始在棋盤的起始點并有起始點所标有的能量。

2.機器人隻能向右或者向下走，并且每走一步消耗一機關能量。

3.機器人不能在原地停留。

4.當機器人選擇了一條可行路徑後，當他走到這條路徑的終點時，他将隻有終點所标記的能量。

如上圖，機器人一開始在(1,1)點，并擁有4機關能量，藍色方塊表示他所能到達的點，如果他在這次路徑選擇中選擇的終點是(2,4)

點，當他到達(2,4)點時将擁有1機關的能量，并開始下一次路徑選擇，直到到達(6,6)點。

我們的問題是機器人有多少種方式從起點走到終點。這可能是一個很大的數，輸出的結果對10000取模。  

Input 第一行輸入一個整數T,表示資料的組數。

對于每一組資料第一行輸入兩個整數n,m(1 <= n,m <= 100)。表示棋盤的大小。接下來輸入n行,每行m個整數e(0 <= e < 20)。  

Output 對于每一組資料輸出方式總數對10000取模的結果.  

Sample Input

1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
        

Sample Output

3948
        

Author xhd  

Source 2008杭電集訓隊選拔賽  

Recommend wangye   |   We have carefully selected several similar problems for you:   1421  1789  1176  1231  2159   這是做的第二個記憶化搜尋的題上一個手poj的滑雪 題目中說每點有各自的能量代表其能到達的範圍發現每一層能到達的距離比上一層減一 僞代碼 for i : 0 to a[i][j] for j: 0 to a[i][j]-i 用dp[i][j]表示第i行第j列到dp[n][m]的走法有幾種初始化dp為0；dp[n][m]=1; 調用遞歸求dp[1][1] ACcode:

#pragma warning(disable:4786)//使命名長度不受限制
#pragma comment(linker, "/STACK:102400000,102400000")//手工開棧
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <stack>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rds(x) scanf("%s",x)
#define rdc(x) scanf("%c",&x)
#define ll long long int
#define maxn 205
#define mod  10000
#define INF 0x3f3f3f3f //int 最大值
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;++i)
#define MT(x,i) memset(x,i,sizeof(x))
#define PI  acos(-1.0)
#define E  exp(1)
using namespace std;
int dp[maxn][maxn];
int a[maxn][maxn];
int loop,n,m;
int dfs(int x,int y){
    int dx,dy;
    if(!dp[x][y]){
    FOR(i,0,a[x][y])
        for(int j=0;j<=a[x][y]-i;++j){
            if(i+j==0)continue;
            dx=x+i;
            dy=y+j;
            if(dx<1||dx>n||dy<1||dy>m);
            else
                dp[x][y]=(dp[x][y]+dfs(dx,dy))%mod;
        }
    }
    return dp[x][y];
}
int main(){
    rd(loop);
    while(loop--){
        rd2(n,m);
        MT(a,0);
        FOR(i,1,n)
            FOR(j,1,m)
                rd(a[i][j]);
        MT(dp,0);
        dp[n][m]=1;
        printf("%d\n",dfs(1,1));
    }
    return 0;
}
/*
1
6 6
4 5 6 6 4 3
2 2 3 1 7 2
1 1 4 6 2 7
5 8 4 3 9 5
7 6 6 2 1 5
3 1 1 3 7 2
*/