poj1088(記憶化搜索)

題意：中文題誒～

思路：dfs，不過直接dfs因該會超時，那我們給他加個記錄路徑就好了．．．

代碼：

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 const int MAXN=1e2+10;
 7 int dp[MAXN][MAXN], mp[MAXN][MAXN];
 8 int dir[4][2]={0, 1, 0, -1, 1, 0, -1, 0};
 9 int n, m, fx, fy;
10 
11 int dfs(int x, int y){
12     if(dp[x][y]) return dp[x][y];
13     for(int i=0; i<4; i++){
14         fx=x+dir[i][0];
15         fy=y+dir[i][1];
16         if(fx>=0&&fx<n&&fy>=0&&fy<m){
17             if(mp[fx][fy]<mp[x][y]){
18                 int cnt=dfs(fx, fy);
19                 if(dp[x][y]<cnt+1){
20                     dp[x][y]=cnt+1;
21                 }
22             }
23         }
24     }
25     return dp[x][y];
26 }
27 
28 int main(void){
29     while(cin >> n >> m){
30         int ans=0;
31         memset(dp, 0, sizeof(dp));
32         for(int i=0; i<n; i++){
33             for(int j=0; j<m; j++){
34                 cin >> mp[i][j];
35             }
36         }
37         for(int i=0; i<n; i++){
38             for(int j=0; j<m; j++){
39                 int cnt=dfs(i, j);
40                 ans=max(ans, cnt);
41             }
42         }
43         cout << ans+1 << endl;
44     }
45     return 0;
46 }

View Code