经典搜索题
題目：http://poj.org/problem?id=1088
?
題意：給一個n*m的矩陣，從矩陣中任意選一點，然后往低處滑，求能滑的最遠長度。
?
分析：典型的記憶化搜索，對于矩陣中每一個點，我們都從該點往低處搜索，記錄最大值，最后對所有的點求最大值即可。
#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 105;int dp[N][N]; int map[N][N]; int n,m;int dfs(int r,int c) {if(dp[r][c]) return dp[r][c];int ans = 0;if(r + 1 <= n && map[r][c] > map[r+1][c]){int tmp = dfs(r+1,c);ans = max(ans,tmp);}if(r - 1 >= 1 && map[r][c] > map[r-1][c]){int tmp = dfs(r-1,c);ans = max(ans,tmp);}if(c + 1 <= m && map[r][c] > map[r][c+1]){int tmp = dfs(r,c+1);ans = max(ans,tmp);}if(c - 1 >= 1 && map[r][c] > map[r][c-1]){int tmp = dfs(r,c-1);ans = max(ans,tmp);}dp[r][c] = ans + 1;return dp[r][c]; }int Work() {int ans = 0;memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dp[i][j] = dfs(i,j);ans = max(ans,dp[i][j]);}}return ans; }int main() {while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&map[i][j]);printf("%d\n",Work());}return 0; }
?
題目：?http://acm.hdu.edu.cn/showproblem.php?pid=1312
?
題意：在一個矩陣中只有紅黑兩種方塊，給定一個點的坐標，從該點出發只能到達黑色的方塊，可以上下左右走，最多能走多
少個黑色方塊？
?
#include <iostream> #include <string.h> #include <stdio.h>using namespace std;int w,h; char s[21][21];int f(int i,int j) {if(i<1||i>h||j<1||j>w)return 0;if(s[i][j]!='#'){s[i][j]='#';return 1+f(i,j-1)+f(i,j+1)+f(i-1,j)+f(i+1,j);}else return 0; }int main() {while(cin>>w>>h){if(w==0&&h==0) break;for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)cin>>s[i][j];for(int i=1;i<=h;i++)for(int j=1;j<=w;j++)if(s[i][j]=='@')cout<<f(i,j)<<endl;}return 0; }
?
總結
