poj 1088 滑雪 (狀態壓縮DP)

題目鏈接: poj 1088

題目大意: 給出NxM的矩陣，每個點的值都不同

若某點四個方向中某個方向的值比它小則可以移動，求能夠走的最長步數

解題思路: 經典的狀態壓縮Dp，Dp[ x ][ y ]記錄從(x , y)點出發能走的最長步數

Dp[ x ][ y ]=Max(Dp[ x ][ y ]，DFS(xx , yy) + 1)

若某個點之前已經走過，則不用再走，直接返回之前所能走到的最大值

代碼:

#include 
#include 
#include 
#define MAX 120
#define Max(a,b) ((a>b)?a:b)
int Map[MAX][MAX],Dp[MAX][MAX];
int n,m,Fx[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

int DFS(int x,int y)
{
    int i,xx,yy;
    if(Dp[x][y]!=0)   //已經搜索過的直接返回
        return Dp[x][y];
    for(i=0;i<4;i++)
    {
        xx=Fx[i][0]+x;
        yy=Fx[i][1]+y;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&Map[x][y]>Map[xx][yy]) //可以往下搜索
            Dp[x][y]=Max(Dp[x][y],DFS(xx,yy)+1);
    }
    return Dp[x][y];  //x,y為起點的最優解
}

int main()
{
    int i,j,M;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        M=0;
        memset(Dp,0,sizeof(Dp));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
                scanf("%d",&Map[i][j]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                Dp[i][j]=DFS(i,j);    //枚舉起點
                M=Max(Dp[i][j],M);
            }
        }
        printf("%d\n",M+1);
    }
    return 0;
}