记忆化搜索TLE一个点求助DaLaos

P1434 [SHOI2002] 滑雪

Clay_L @ 2023-01-31 11:24:28

代码:

#include<bits/stdc++.h>
using namespace std;
int n,m,a[111][111],f[111][111],ans;
int dx[5]={-1,0,1,0,0},dy[5]={0,1,0,-1,0};
int dfsp(int x,int y)
{
    int t=f[x][y],xx,yy;
    if(t!=-1) return t;
    t=1;
    for(int i=0;i<4;i++)
    {
        xx=x+dx[i],yy=y+dy[i];
        if((xx<1||xx>n||yy<1||yy>m)||a[x][y]<=a[xx][yy]) continue;
        t=max(t,dfsp(xx,yy)+1);
    }
    return t;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j],f[i][j]=-1;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) ans=max(ans,dfsp(i,j));
    cout<<ans<<endl;
    return 0;
}

by Siegerkranz_2735 @ 2023-01-31 13:57:28


by Clay_L @ 2023-01-31 14:08:36

I'm very 无语


by Stephen_Curry_bean @ 2023-02-02 15:26:11

广搜的框架 前期的准备:一个队列,还有以个伴随的hash表

  1. 把起始结点放入队列
  2. 如果队列不为空,那么从队列中反复取头结点。
  3. 对于取出的头结点,进行扩展,把没有进过队列的新结点,加入队列中,并
  4. 在hash中做好标记。

by Clay_L @ 2023-02-08 17:23:34

@Stephen_Curry_bean 栓Q啦


上一页 |