第二个点T了

P1434 [SHOI2002] 滑雪

LHLeisus @ 2022-01-25 10:33:37

#include<iostream>

using namespace std;
int r,c,ans=-1;
int h[105][105];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool vis[105][105];
bool in(int x,int y)
{
    if(x>=1&&y>=1&&x<=r&&y<=c&&!vis[x][y])
        return true;
    else 
        return false;
}
void dfs(int x,int y,int w)
{
    if(w>r*c) return;
    ans=max(ans,w);
    for(int i=0;i<=3;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(in(nx,ny)&&h[nx][ny]<h[x][y])
        {
            vis[nx][ny]=true;
            dfs(nx,ny,w+1);
            vis[nx][ny]=false;
        }
    }
}
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>h[i][j];
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
        {
            vis[i][j]=true;
            dfs(i,j,1);
            vis[i][j]=false;
        }
    cout<<ans;
    return 0;
}

by LJCzzzzZ @ 2022-02-22 16:31:59

你这没有记忆化你可能在后面的dfs中又遍历了之前遍历过的情况就超时了 参考斐波那契


|