TLE#3#10求优化
查看原帖
TLE#3#10求优化
370577
BigBen2020楼主2022/8/10 12:48

评测记录:link

//连通块
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int MAXN = 1050;
int n;
int w[MAXN][MAXN];
bool used[MAXN][MAXN];
struct point{
    int x_;
    int y_;
};
queue<point>q;
int dx[9] = {0,1,0,-1,1,-1,0,-1,1};
int dy[9] = {0,1,1,1,-1,-1,-1,0,0};
//八连通
int fg,ff;
//非谷,非峰
int a;

void bfs(int x,int y){
    if(used[x][y]){
        //在其他连通块中处理过
        return ;
    }
    bool srch[MAXN][MAXN];
	 memset(srch,false,sizeof(srch));
	  srch[x][y] = true;
    a++;
    used[x][y] = true;
    point tmp;
    tmp.x_ = x;
    tmp.y_ = y;
    q.push(tmp);
    bool flag1,flag2;
    //是峰?是谷?
    flag1 = flag2 = true;
    while(!q.empty()){
        point b;
        b = q.front();
        q.pop();
        for(int i = 1;i<=8;i++){
            point c;
            c.x_ = b.x_ + dx[i];
            c.y_ = b.y_ + dy[i];
            if(c.x_<=0||c.x_>n||c.y_<=0||c.y_>n){
                continue;
            }
            if(srch[c.x_][c.y_]){
                continue;
            }
            if(w[c.x_][c.y_]==w[b.x_][b.y_]){
                q.push(c);
                //连通块设定
                used[c.x_][c.y_] = true;
                srch[c.x_][c.y_] = true;
            }
            else{
                if(w[c.x_][c.y_]>w[b.x_][b.y_]){
                    //不是山峰 
                    flag1 = false;
                }
                else{
                    flag2 = false;
                }
            }
        }
    }
    if(flag1==false){
        ff++;
    }
    if(flag2==false){
        fg++;
    }
    return ;
}
void method_1(){
    scanf("%d",&n);
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            scanf("%d",&w[i][j]);
        }
    }
    fg = ff = 0;
    a = 0;
    memset(used,false,sizeof(used));
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            bfs(i,j);
        }
    }
    int f,g;
    g = a - fg;
    f = a - ff;
    printf("%d %d",f,g);
    return ;
}
int main(){
    method_1();
    return 0;
}

应该是memset(srch,0,sizeof(srch))爆了。 求助

2022/8/10 12:48
加载中...