bfs写法好像不太对,蒟蒻求助呜呜呜
查看原帖
bfs写法好像不太对,蒟蒻求助呜呜呜
843596
Otion楼主2023/1/4 14:30
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;
struct node
{
    int num = 0;
    int row;
    int col;
    bool viewed = false;
} map[105][105];
//每个点里面的row和col都还没定义,等下面用到他们的时候会定义哦
int total_row;
int total_col;
int count;
queue<node> line;
int shift_x[] = {-1, 1, 0, 0};
int shift_y[] = {0, 0, -1, 1};
void bfs(int row, int col)
{
    count++;
    line.push(map[row][col]);
    map[row][col].viewed = true;
    while (!line.empty())
    {
        int front_x = line.front().row;
        int front_y = line.front().col;
        for (int i = 0; i < 4; i++)
        {
            if (map[front_x + shift_x[i]][front_y + shift_y[i]].viewed == false)
            {
                if (map[front_x + shift_x[i]][front_y + shift_y[i]].num > 0)
                {
                    line.push(map[front_x + shift_x[i]][front_y + shift_y[i]]);
                    map[front_x + shift_x[i]][front_y + shift_y[i]].viewed = true;
                    map[front_x + shift_x[i]][front_y + shift_y[i]].row = front_x + shift_x[i];
                    map[front_x + shift_x[i]][front_y + shift_y[i]].col = front_y + shift_y[i];
                }
            }
        }
        line.pop();
    }
}
int main()
{
    cin >> total_row >> total_col;
    for (int j = 0; j < total_row; j++)
    {
        for (int k = 0; k < total_col; k++)
        {
            scanf("%1d", &map[j][k].num);
        }
    }
    for (int i = 0; i < total_row; i++)
    {
        for (int k = 0; k < total_col; k++)
        {
            map[i][k].row = i;
            map[i][k].col = k;
            if (map[i][k].viewed == false && map[i][k].num > 0)
            {
                bfs(i, k);
            }
        }
    }
    cout << count << endl;
    return 0;
}
2023/1/4 14:30
加载中...