【NOIP模拟赛180503】活蹦乱跳的香穗子

题目描述

香穗子在田野上调蘑菇!她跳啊跳,发现自己很无聊,于是她想了一个有趣的事情,每个格子最多只能经过1次,且每个格子都有其价值

跳的规则是这样的,香穗子可以向上下左右四个方向跳到相邻的格子,并且她只能往价值更高(这里是严格的大于)的格子跳.

香穗子可以从任意的格子出发,在任意的格子结束,

那么她最多能跳几次?

输入

第一行n,m,表示田野的长和宽

接下来n行,每行m个数,表示该格的价值

输出

一个数,表示最多跳得次数

样例输入

2 2
2 5
-1 3

样例输出

2

提示

n,m<=100

答案保正小于Maxlongint

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,g[101][101];
struct Point{
    int x,y;
}q[1000000];
int dis[101][101];
int ans=0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs(int xx,int yy)
{
    memset(dis,-1,sizeof(dis));
    int f=1,e=1;
    Point s;
    s.x=xx,s.y=yy,dis[xx][yy]=0;
    q[1]=s;
    while(f<=e)
    {
        Point u=q[f++];
        for(int i=0;i<4;i++)
        {
            Point v;
            v.x=u.x+dx[i],v.y=u.y+dy[i];
            if(v.x<1||v.x>n||u.y<1||v.y>m) continue;
            if(g[v.x][v.y]<=g[u.x][u.y]) continue;
            if(dis[v.x][v.y]>=dis[u.x][u.y]+1) continue;
            dis[v.x][v.y]=dis[u.x][u.y]+1;
            if(dis[v.x][v.y]>ans) ans=dis[v.x][v.y];
            q[++e]=v;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&g[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            bfs(i,j);
        }
    cout<<ans<<endl;
    return 0;
}