【HDOJ】1978 How many ways

DFS。

 #include <stdio.h>

 #include <string.h>

 #define MAXNUM 105

 int map[MAXNUM][MAXNUM], ways[MAXNUM][MAXNUM], n, m;

 int dfs(int x, int y) {

     int i, j, way=;

     if (ways[x][y])

         return ways[x][y];

     for (i=; i<=map[x][y]; ++i) {

         for (j=; i+j<=map[x][y]; ++j) {

             if (i== && j==)

                 continue;

             if (x+i>=n || y+j>=m)

                 continue;

             way += dfs(x+i, y+j);

             if (way >= )

                 way %= ;

         }

     }

     ways[x][y] = way;

     return way;

 }

 int main() {

     int t;

     int i, j;

     scanf("%d", &t);

     while (t--) {

         scanf("%d %d", &n, &m);

         memset(ways, , sizeof(ways));

         for (i=; i<n; ++i)

             for (j=; j<m; ++j)

                 scanf("%d", &map[i][j]);

         ways[n-][m-] = ;

         i = dfs(, );

         printf("%d\n", i);

     }

     return ;

 }