求助 bfs为什么会MLE
查看原帖
求助 bfs为什么会MLE
891139
BoBolilla楼主2023/8/26 16:09
#include<iostream>
#include <cmath>
#include <algorithm>
#include <stack>
#include<vector>
#include<queue>
#include <cstring>
#include <iomanip>
#define endl "\n"
//#define LL long long
#define int long long
#define PII pair<int,int>
using namespace std;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};


const int N = 1010;
char g[N][N];
bool vis[N][N],flag;
int n;

void bfs(int x,int y)
{
    
    queue<PII>q;
    q.push({x,y});
    while(q.size())
    {
        auto t=q.front();q.pop();
        int tx=t.first;int ty=t.second;
        vis[tx][ty]=1;
         if(g[tx-1][ty]=='#'&&g[tx+1][ty]=='#'&&g[tx][ty-1]=='#'&&g[tx][ty+1]=='#') flag = 1;
    for(int i=0;i<4;i++)
    {
       int  xx=tx+dx[i],yy=ty+dy[i];
        if(g[xx][yy]=='#'&&!vis[xx][yy])
        {
            q.push({xx,yy});
        }
    }
    }
}


signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i=0;i<n;i++) cin >> g[i];

    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(g[i][j]=='#'&&!vis[i][j])
            {
                flag=0;
                bfs(i,j);
                if(!flag) ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

不开O2tle,开O2mle 只有36分

2023/8/26 16:09
加载中...