求助找BUG

P1434 [SHOI2002] 滑雪

xueliyuan @ 2020-07-30 16:18:02

大佬们,求助一下,帮帮我吧谢啦!!☆⌒(*^-゜)v

1,3,6,9 AC

2 TLE

其他全WA

样例过了

不能下载数据这就很抓狂!!!

我主要是DFS思路,首先2重循环枚举开始点,再用DFS搜索上下左右四个方向。如果走过了用flag标记一下,在判断边界,走没做过,有没有比所在点高,接着继续递归搜索一下。用一个步数参数step,然后用maxn更新它。最后输出maxn(具体一会看程序)

假如我们先不考虑超时情况,那么这个代码怎么改?

( ̄ ‘i  ̄;)

#include<bits/stdc++.h>
using namespace std;
int Map[101][101];
bool flag[101][101];
int n,m;
int maxn=-1;
void dfs(int a,int b,int step)
{
    memset(flag,0,sizeof(flag));
    if(a<n&&flag[a+1][b]==0&&Map[a][b]>Map[a+1][b])
    {
        dfs(a+1,b,step+1);
        flag[a+1][b]=1;
    }
    if(b<m&&flag[a][b+1]==0&&Map[a][b]>Map[a][b+1])
    {
        dfs(a,b+1,step+1);
        flag[a][b+1]=1;
    }
    if(a>0&&flag[a-1][b]==0&&Map[a][b]>Map[a-1][b])
    {
        dfs(a-1,b,step+1);
        flag[a-1][b]=1;
    }
    if(b>0&&flag[a][b-1]==0&&Map[a][b]>Map[a][b-1])
    {
        dfs(a,b-1,step+1);
        flag[a][b-1]=1;
    }
    maxn=max(maxn,step);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>Map[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dfs(i,j,0);
        }
    }
    cout<<maxn;
    return 0;
}

谢谢大佬们啦!


by 无秒 @ 2020-07-30 16:54:17

首先,您这个flag会导致WA。怎么说呢,比如当搜索到x,y时,step为4,但是后面再搜时这个step可能更加高为5,但是你标记了所以就不能搜下去。

把你的程序改了改,90,加上记忆化就好。

#include<bits/stdc++.h>
using namespace std;
int Map[101][101];
int n,m;
int maxn=-1;

void dfs(int a,int b,int step)
{
    if(a<n&&Map[a][b]>Map[a+1][b])
    {
        dfs(a+1,b,step+1);
    }
    if(b<m&&Map[a][b]>Map[a][b+1])
    {
        dfs(a,b+1,step+1);
    }
    if(a>1&&Map[a][b]>Map[a-1][b])
    {
        dfs(a-1,b,step+1);
    }
    if(b>1&&Map[a][b]>Map[a][b-1])
    {
        dfs(a,b-1,step+1);
    }
    maxn=max(maxn,step);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>Map[i][j];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dfs(i,j,1);
        }
    }
    cout<<maxn;
    return 0;
}

by 无秒 @ 2020-07-30 16:54:54

还是写了个“你”,是“您”,我的错好吧


by 无秒 @ 2020-07-30 16:57:04

而且一开始是从1开始的,您不走它也有一步是不是


by 无秒 @ 2020-07-30 17:00:00

@xueliyuan萌新太菜了qwq


by xueliyuan @ 2020-07-31 14:38:50

@无秒 好的,谢谢您( ̄▽ ̄)"


上一页 |