bfs 36分求调整

lixxyu11 @ 2023-04-06 12:00:08

#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;
char a[N][N];
bool st[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int n, res, nx, ny;
int total, bound;
bool bound_is;
typedef pair<int, int> PII;
queue<PII> q;
void bfs(int x, int y, int total, int bound)
{

    q.emplace(x, y);
    while (q.size())
    {
        auto c = q.front();
        q.pop();
        int sx = c.first;
        int sy = c.second;
        total++;
        st[sx][sy] = true;
        bound_is=false;
        for (int i = 0; i < 4; i++)
        {
            nx = sx + dx[i];
            ny = sy + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (a[nx][ny] == '.')
            {
                bound_is = true;
                continue;
            }
            if (!st[nx][ny])
            {

                q.emplace(nx, ny);
            }
        }
        if (bound_is == true)
            bound++;
    }
    if (bound == total)
        res++;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!st[i][j] && a[i][j] == '#')
            {
                total = 0, bound = 0;
                bfs(i, j, total, bound);
            }
        }
    }
    cout << res;
    return 0;
}

by lixxyu11 @ 2023-04-06 12:02:07

只能对三组数据，其他全部tle了，但如果在判断岛屿中加入标记就能过了不知道为什么

#include <queue>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1010;
char a[N][N];
bool st[N][N];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};

int n, res, nx, ny;
int total, bound;
bool bound_is;
typedef pair<int, int> PII;
queue<PII> q;
void bfs(int x, int y, int total, int bound)
{

    q.emplace(x, y);
    while (q.size())
    {
        auto c = q.front();
        q.pop();
        int sx = c.first;
        int sy = c.second;
        total++;
        st[sx][sy] = true;
        bound_is=false;
        for (int i = 0; i < 4; i++)
        {
            nx = sx + dx[i];
            ny = sy + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= n)
                continue;
            if (a[nx][ny] == '.')
            {
                bound_is = true;
                continue;
            }
            if (!st[nx][ny])
            {
                st[nx][ny]=true;
                q.emplace(nx, ny);
            }
        }
        if (bound_is == true)
            bound++;
    }
    if (bound == total)
        res++;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (!st[i][j] && a[i][j] == '#')
            {
                total = 0, bound = 0;
                bfs(i, j, total, bound);
            }
        }
    }
    cout << res;
    return 0;
}