90分求助，RE第二个点

SheKong @ 2019-04-23 14:10:39

#include<cstdio>
int r,c,map[101][101],step[101][101],X[150*150],Y[150*150];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1},ans=1;
void bfs(int xx,int yy)
{
    X[1]=xx;Y[1]=yy;step[xx][yy]=1;
    int head=1,tail=1,x,y;
    while(head<=tail)
    {
        x=X[head];y=Y[head++];
        int i;
        for(i=0;i<4;i++)
        {
            if(x+dx[i]>=1&&x+dx[i]<=r&&y+dy[i]>=1&&y+dy[i]<=c)
            {
                if(map[x+dx[i]][y+dy[i]]<map[x][y]&&step[x][y]+1>step[x+dx[i]][y+dy[i]])
                {
                    tail++;
                    X[tail]=x+dx[i];Y[tail]=y+dy[i];
                    step[X[tail]][Y[tail]]=step[x][y]+1;
                    ans=step[X[tail]][Y[tail]]>ans?step[X[tail]][Y[tail]]:ans;
                }
            }
        }
    }
    for(int i=1;i<=tail;i++)
    {
        step[X[i]][Y[i]]=0;
        X[i]=0;Y[i]=0;
    }
}
int main()
{
    scanf("%d %d",&r,&c);
    int i,j;
    for(i=1;i<=r;i++)for(j=1;j<=c;j++)scanf("%d",&map[i][j]);
    for(i=1;i<=r;i++)
    {
        for(j=1;j<=c;j++)
        {
            bfs(i,j);
        }
    }
    printf("%d",ans);
    return 0;
}

by SheKong @ 2019-04-23 14:11:25

28ms 824kB

by 龙之吻—水货 @ 2019-04-23 15:01:26

@SheKong 这题是记忆化搜索鸭，你直接 BFS 会炸的 QwQ

by SheKong @ 2019-04-24 13:22:31

@龙之吻—水货 QWQ 可是我其它点都过了呀

by 樱花飞舞 @ 2019-04-27 09:53:27

我也不懂为什么，这是我去年写的90分程序

#include<cstdio>
#include<cstring>
int max(int x, int y)
{
    return x > y ? x : y;
}
const int dx[] = { 0,1,-1,0 };
const int dy[] = { 1,0,0,-1 };
struct MyStruct
{
    int x, y, d;
}h[10002];
int n, m, a[101][101];
bool v[101][101];
int bfs(int, int);
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    int maxn = -99999;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            int temp = bfs(i, j);
            maxn = max(temp, maxn);
        }
    printf("%d", maxn+1);
}
int bfs(const int start_x, const int start_y)
{
    h[1].x = start_x;
    h[1].y = start_y;
    h[1].d = 1;
    v[start_x][start_y] = 1;
    int tail = 1, head = 0;
    while (tail > head)
    {
        head++;
        for (int i = 0; i <= 3; i++)
        {
            int x = h[head].x + dx[i];
            int y = h[head].y + dy[i];
            if (x > 0 && y > 0 && x <= n && y <= m && a[x][y] < a[h[head].x][h[head].y])
            {
                tail++;
                h[tail].x = x;
                h[tail].y = y;
                h[tail].d = h[head].d + 1;
            }
        }
    }
    memset(v, 0, sizeof(v));
    return h[tail].d-1;
}

然后现在换了一种思路，AC

#include<cstdio>
const int INF_INT = 99999999;
const int   dx[] = { 0,1,-1,0 },
            dy[] = { 1,0,0,-1 };
int n, m, a[105][105], f[105][105];
inline int max(int x, int y)
{
    return x > y ? x : y;
}
int go(int x, int y)
{
    if (f[x][y] > 0)
        return f[x][y];
    int t = 0, temp = 0;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + dx[i],
            yy = y + dy[i];
        if (xx > 0 && yy > 0 && xx <= n && yy <= m && a[xx][yy] < a[x][y])
        {
            temp = go(xx, yy) + 1;
            t = max(t, temp);
        }
    }
    f[x][y] = t;
    return t;
}
int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &a[i][j]);
    int ans = - INF_INT;
    for(int i=1,t;i<=n;i++)
        for (int j = 1; j <= m; j++)
        {
            t = go(i, j);
            ans = max(t, ans);
        }
    printf("%d\n", ans+1);
}

by Dasknight @ 2019-04-27 11:45:36

我跑DJ也WA了第二个点

by SheKong @ 2019-04-27 12:01:14

我RE的原因究竟是什么呢awa