HDU1978 How many ways 动态规划

题意就不多说了，刚开始还在用搜索来写，定了两个方向，标记去重，各种，然后就TLE了。

正解就是枚举行方向的量，再控制列方向的量，使得行和列上的偏移量不超过规定的步数即可，在没有每一次memset的情况下，注意在枚举的时候去掉自己这个点。

代码如下：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#define MOD 10000
#define MAXN 105
using namespace std;

int G[MAXN][MAXN], n, m;

int dp[MAXN][MAXN];

inline int dist(int x, int y)
{
    return n-x+m-y;
}

inline bool judge(int x, int y)
{
    if (x >= 1 && x <= n && y >= 1 && y <= m) {
        return true;
    }
    else {
        return false;
    }
}

int DFS(int x, int y, int step)
{
    int sum = 0;
    for (int i = 0; i <= step; ++i) {
        for (int j = 0; i+j <= step; ++j) {
            if (judge(x+i, y+j) && !(i==0 && j==0)) {
                sum += dp[x+i][y+j];
                if (sum >= MOD) {
                    sum %= MOD;
                }
            }
        }
    }
    return sum;
}

int DP()
{
    for (int i = n; i >= 1; --i) {
        for (int j = m; j >= 1; --j) {
            if (i == n && j== m) {
                dp[i][j] = 1;
            }
            else if (G[i][j]){ 
                dp[i][j] = DFS(i, j, G[i][j]);
            }
            else {
                dp[i][j] = 0;
            }
        }
    }
    return dp[1][1];
}

void getint( int &c )
{
    char chr;
    while( chr= getchar(), chr< '0'|| chr> '9' ) ;
    c= chr- '0';
    while( chr= getchar(), chr>= '0'&& chr<= '9' )
    {
        c=c* 10+ chr- '0';
    }
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                getint(G[i][j]);
            }
        }
        printf("%d\n", DP());
    }    
    return 0;
}