神奇的错误

P1434 [SHOI2002] 滑雪

BiaxialRay @ 2019-09-13 14:42:01

WA #7 #8,找了好久都没有找出错误

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int Max = 2e2 + 50;
int n,m,ans;
int map[Max][Max],d[Max][Max];
int dx[] = {0,1,-1,0,0};
int dy[] = {0,0,0,1,-1};

int fmax(int a,int b){
    if(a > b)return a;
    return b;
}

struct node{
    int x;
    int y;
}a[Max*Max];

int cmp(node a,node b){
    return map[a.x][a.y] > map[b.x][b.y];
}

int main(){
    int i,j,nx,ny;
    scanf("%i%i",&n,&m);
    memset(map,0,sizeof(map));
    memset(d,0,sizeof(d));
    for(i = 1;i <= n;i++){
        for(j = 1;j <= m;j++){
            d[i][j] = 1;
            scanf("%i",&map[i][j]);
            a[(i-1)*m+j].x = i;
            a[(i-1)*m+j].y = j;
        }
    }

    sort(a+1,a+n*m+1,cmp);
//  for(i = 1;i <= n;i++){
//      for(j = 1;j <= m;j++){
//          printf("%i,%i ",a[(i-1)*m+j].x,a[(i-1)*m+j].y);
//      }
//      printf("\n");
//  }
//  for(i = 1;i <= n*m;i++){
//      printf("%i ",map[a[i].x][a[i].y]);
//      
//  }

    for(i = 1;i <= n*m;i++){
        for(j = 1;j <= 4;j++){
            nx = a[i].x + dx[j];
            ny = a[i].y + dy[j];
            if(nx < 1 || ny < 1 || nx > n || ny > m)continue;
            if(map[nx][ny] < map[a[i].x][a[i].y])d[nx][ny] = fmax(d[nx][ny],d[a[i].x][a[i].y] + 1);

        }
    }
    ans = 1;
    for(i = 1;i <= n;i++){
        for(j = 1;j <= m;j++){
            ans = fmax(ans,d[i][j]);
        }
    }
//  for(i = 1;i <= n;i++){
//      for(j = 1;j <= m;j++){
//          printf("%i ",d[i][j]);
//      }
//      printf("\n");
//  }
    printf("%i",ans);
    return 0;
}

by QQ893531942 @ 2019-09-13 15:47:14

您代码56行d[a[i].x][a[i].y]不一定已求出。


by BiaxialRay @ 2019-09-13 19:15:53

@QQ893531942 我把所有的都初始化为1了,抱歉,没加注释有点不太明显


by BiaxialRay @ 2019-09-13 19:17:01

@QQ893531942 我做另一道几乎一模一样的题全A了,这道题WA了2个


by BiaxialRay @ 2019-09-14 08:55:16

@QQ893531942 把输入中的%i改成%d就AC了,真特娘的精彩


|