学步园

小记：我利用前面的值来更新当前值的方法 硬是想不通哪里错了，只能用向后的了

思路：每格最大值为20， 

我们对每个值 更新其所能到达的位置的值， 保存的是放法数

那么时间复杂度就是O(n*m*20*20)  1s内是可以的

code :

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8

const int MAX_ = 110;
const int N = 1010;
const int INF = 0x7fffffff;
const int M = 10000;

int dp[MAX_][MAX_];
int p[MAX_][MAX_];


int main(){
	int n, m, ans;
    int T;
    scanf("%d", &T);

	while(T--){
	    scanf("%d%d", &n, &m);

        REP(j, 1, n+1){
            REP(i, 1, m+1){
                scanf("%d", &p[j][i]);
            }
        }
        
        REP(k, 0, n+1)REP(i, 0, m+1)
                dp[k][i] = 0;


        dp[1][1] = 1;

        REP(i, 1, n+1){
            REP(j, 1, m+1){
                //if(i == 1 && j == 1)continue;
                dp[i][j] %= M;
                
                for(int k = i; k <= p[i][j] + i && k <= n; ++k){
                    for(int r = j; r <= p[i][j] + j && r <= m; ++r){
                        if(k == i && r == j)    continue;
                        if(p[i][j] >= k + r - i - j)
                            dp[k][r] += dp[i][j];
                    }
                }

                //printf("%d ", dp[i][j]);
            }
            //printf("\n");
        }
        dp[n][m] %= M;

        printf("%d\n", dp[n][m]);
	}
	return 0;
}