POJ 2704 Pascals Travels (記憶化搜索裸題)

 


 
#include <cstdio>   
#include <iostream>   
#include <cstring>   
using namespace std;  
char str[44][44];  
int map[44][44],vis[44][44];  
__int64 dp[44][44];  
int n;  
int dirx[2] = {0,1};  
int diry[2] = {1,0};  
void init() {  
    memset(dp,0,sizeof(dp));  
    memset(map,0,sizeof(map));  
    memset(vis,0,sizeof(vis));  
}  
  
bool inside(int i,int j) {  
    if(i<0 || i>=n || j<0 || j>=n) return false;  
    return true;  
}  
  
__int64 dfs(int x,int y) {  
    if(dp[x][y] != 0) {  
      //  cout << x << ' ' << y << ' ' << dp[x][y] << endl;   
        return dp[x][y];  
    }  
    if(x == n-1 && y == n-1) return 1;  
    for(int i=0; i<2; i++) {  
        int xx = x + dirx[i] * map[x][y];  
        int yy = y + diry[i] * map[x][y];  
        if(inside(xx,yy) && vis[xx][yy] == 0) {  
            vis[xx][yy] = 1;  
            dp[x][y] += dfs(xx,yy);  
            vis[xx][yy] = 0;  
        }  
    }  
   // cout << x << ' ' << y << ' ' << dp[x][y] << endl;   
    return dp[x][y];  
}  
  
int main() {  
  
    int i,j;  
    while(scanf("%d",&n)) {  
        if(n == -1) break;  
        init();  
        for(i=0; i<n; i++) {  
            scanf("%s",str[i]);  
        }  
        for(i=0; i<n; i++) {  
            for(j=0; j<n; j++) {  
                map[i][j] = str[i][j] - '0';  
            }  
        }  
        vis[0][0] = 1;  
        printf("%I64d\n",dfs(0,0));  
    }  
    return 0;  
}  

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
char str[44][44];
int map[44][44],vis[44][44];
__int64 dp[44][44];
int n;
int dirx[2] = {0,1};
int diry[2] = {1,0};
void init() {
    memset(dp,0,sizeof(dp));
    memset(map,0,sizeof(map));
    memset(vis,0,sizeof(vis));
}

bool inside(int i,int j) {
    if(i<0 || i>=n || j<0 || j>=n) return false;
    return true;
}

__int64 dfs(int x,int y) {
    if(dp[x][y] != 0) {
      //  cout << x << ' ' << y << ' ' << dp[x][y] << endl;
        return dp[x][y];
    }
    if(x == n-1 && y == n-1) return 1;
    for(int i=0; i<2; i++) {
        int xx = x + dirx[i] * map[x][y];
        int yy = y + diry[i] * map[x][y];
        if(inside(xx,yy) && vis[xx][yy] == 0) {
            vis[xx][yy] = 1;
            dp[x][y] += dfs(xx,yy);
            vis[xx][yy] = 0;
        }
    }
   // cout << x << ' ' << y << ' ' << dp[x][y] << endl;
    return dp[x][y];
}

int main() {

    int i,j;
    while(scanf("%d",&n)) {
        if(n == -1) break;
        init();
        for(i=0; i<n; i++) {
            scanf("%s",str[i]);
        }
        for(i=0; i<n; i++) {
            for(j=0; j<n; j++) {
                map[i][j] = str[i][j] - '0';
            }
        }
        vis[0][0] = 1;
        printf("%I64d\n",dfs(0,0));
    }
    return 0;
}