BFS WA 一个点

Moeebius @ 2021-08-04 18:31:07

#include <bits/stdc++.h>
using namespace std;
struct point{
    int x,y,step;
};
point q[10000000],s;
int used[1001][1001],front,tail,n,m,a[1001][1001];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

void bfs(){
    //int step=0;
    front=tail=1;
    //memset(used,0,sizeof(used));
    q[1]=s;
    used[s.x][s.y]=s.step;
    while(front<=tail){
        point u=q[front++];
        point v;
        for(int i=0; i<4; i++){
            v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;
            if(v.x<1||v.x>n||v.y<1||v.y>m) continue;
            if(used[v.x][v.y]>v.step) continue;
            if(a[v.x][v.y]>=a[u.x][u.y]) continue;
            q[++tail]=v;
            used[v.x][v.y]=v.step;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&a[i][j]);
        }
    }
    s.step=1;
    int ans=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(used[i][j]==0){
                s.x=i;
                s.y=j;
                bfs();
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(used[i][j]>ans) ans=used[i][j];
        }
    }
    cout<<ans;
    return 0;
}

by 陈麒麟果 @ 2021-08-15 10:14:46

#include<bits/stdc++.h>
using namespace std;
int maps[110][110];
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int ans[110][110];
int n,m;
int dfs(int x,int y){
    int t = 0; 
    for(int i = 0;i<4;i++){
        int tx = dir[i][0]+x;
        int ty = dir[i][1]+y;
        if(tx<1 || tx>n || ty<1 || ty>m || maps[tx][ty]>=maps[x][y])
            continue;
        if(ans[tx][ty]) t = max(t,ans[tx][ty]);
        else t = max(t,dfs(tx,ty)); 
    } 
    return ans[x][y] = t+1;
}
int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++)
            cin>>maps[i][j];
    }
    int sum = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++){
            sum = max(sum,dfs(i,j));
        }
    }
    cout<<sum<<endl;
    return 0;
}

by Moeebius @ 2021-10-04 13:38:13

#include <bits/stdc++.h>
using namespace std;
struct point{
    int x,y,step;
};
point q[10000001],s;
int used[1001][1001],front,tail,n,m,a[1001][1001];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};

void bfs(){
    //int step=0;
    front=tail=1;
    //memset(used,0,sizeof(used));
    q[1]=s;
    used[s.x][s.y]=s.step;
    while(front<=tail){
        point u=q[front++];
        point v;
        for(int i=0; i<4; i++){
            v.x=u.x+dx[i],v.y=u.y+dy[i],v.step=u.step+1;
            if(v.x<1||v.x>n||v.y<1||v.y>m) continue;
            if(used[v.x][v.y]>v.step) continue;
            if(a[v.x][v.y]>=a[u.x][u.y]) continue;
            q[++tail]=v;
            used[v.x][v.y]=v.step;
        }
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            scanf("%d",&a[i][j]);
        }
    }

    int ans=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(used[i][j]==0){
                s.step=1;
                s.x=i;
                s.y=j;
                bfs();
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(used[i][j]>ans) ans=used[i][j];
        }
    }
    cout<<ans;
    return 0;
}

by Moeebius @ 2021-10-04 13:38:47

what?为什么不开O2WA，开O2RE?

by Moeebius @ 2021-10-04 13:38:59

@陈麒麟果