POJ1008(滑雪)dfs经典中的经典

dfs基础+dp基础
加上一点点记忆化搜索

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int mat[105][105];
int dp[105][105];
int vis[105][105];
int n,m;
bool ok(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;
}
int dirx[]={0,1,0,-1};
int diry[]={1,0,-1,0};
int dfs(int x,int y){
    int nx=0,ny=0;int mx=0;
    if(dp[x][y])return dp[x][y];
    for(int i=0;i<4;i++){
        nx=x+dirx[i];
        ny=y+diry[i];
        if(ok(nx,ny)&&mat[nx][ny]<mat[x][y]){
            dp[nx][ny]=dfs(nx,ny);
            mx=max(mx,dp[nx][ny]);
        }
    }
    return mx+1;
}
int main()
{
    ios::sync_with_stdio(false);
    int i,j,k;
    while(cin>>n>>m){
        memset(dp,0,sizeof dp);
        memset(mat,0,sizeof mat);
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                cin>>mat[i][j];
            }
        }
        int ans=0;
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                ans=max(ans,dfs(i,j));
            }
        }cout<<ans<<endl;
    }
    return 0;
}