huaxuewenti.cpp

滑雪问题

#include<iostream>
using namespace std;

const int MAX = 102;

struct pos
{
    int i,j,p;//i->行;j->列；p->来源方向
};

int path(int [MAX][MAX],int [MAX][MAX],int[][MAX],int,int);

int main()
{
    int input[MAX][MAX];
    int result[MAX][MAX];
    int status[MAX][MAX];
    int m,n;
    int i,j;
    int max,ans;
	cout<<"请输入行数和列数：";
    cin>>m>>n;
    for (i = 0; i<=m+1; i++)
        for (j = 0; j<=n+1; j++)
        {
            input[i][j] = 10001;
            result[i][j] = 0;
            status[i][j] = 0;
        }
cout<<"请输入数值：";
    for (i = 1; i<=m; i++)
        for (j = 1; j<=n; j++)
        {
            cin>>input[i][j];
        }

    for (i = 1; i<=m; i++)
        for (j = 1; j<=n; j++)
            path(input,result,status,i,j);
    
    max = 0;
    for (i = 1; i<=m; i++)
        for (j = 1; j<=n; j++)
            if (max<result[i][j])
                max = result[i][j];

    cout<<max<<endl;
    return 0;
}

int path(int input[MAX][MAX],int result[MAX][MAX],int status[MAX][MAX],int i,int j)
{
    pos pack[MAX*MAX];
    int max,g,h;
    int ii;
    int top = 0;
    int p = 0;
    int incr[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};//增量表
    
    //初始化
    if (result[i][j]>0)
    {
        return 0;
    }
    else 
    {
        pack[top].i = i;
        pack[top].j = j;        
        pack[top].p = p;
        status[i][j] = -1;    
    }

    while (top>=0||p<4)
    {
        if (p<4)
        {
            g = pack[top].i+incr[p][0];
            h = pack[top].j+incr[p][1];
            //判断是否合法
            if (input[pack[top].i][pack[top].j]>input[g][h])
            {
               if (result[g][h]>0||status[g][h]==-1)//
                   p++;
               else
               {
                   //进栈
                   top++;
                   pack[top].i = g;
                   pack[top].j = h;
                   pack[top].p = p;
                   status[g][h] = -1;
                   p = 0;
               }
            }//合法
            else
            {
                p++;
            }
        }
        else//p==4时
        {
            max = 0;
            for (ii = 0; ii<4; ii++)//四个方向
            {
                g = pack[top].i+incr[ii][0];
                h = pack[top].j+incr[ii][1]; 
                if (input[pack[top].i][pack[top].j]>input[g][h]&&max<result[g][h])
                    max = result[g][h];
            }
            result[pack[top].i][pack[top].j] = max+1;
            top--;//回溯
            p = pack[top].p+1;    
        }
    }
    return 0;
}