#include<iostream>
using namespace std;
#define MaxSize 1000
typedef struct
{
int x;
int y;
}QueueNode;
typedef struct
{
QueueNode data[MaxSize];
int rear;//队尾
int front;//队头
}SqQueue;
void enQueue(SqQueue *queue,int x, int y)
{
queue->rear = (queue->rear + 1) % MaxSize;
queue->data[queue->rear].x = x;
queue->data[queue->rear].y = y;
}
void deQueue(SqQueue* queue,int grid[][5])
{
int x = queue->data[queue->front].x;
int y = queue->data[queue->front].y;
//即使队头移动了数据还是会保留在数组里导致当队尾遍历到该位置一样使用
grid[x][y] = 0;
queue->front = (queue->front + 1) % MaxSize;
}
bool isEmpty(SqQueue* queue)
{
if (queue->rear== queue->front)
return true;
else
return false;
}
bool isFull(SqQueue* queue)
{
if ( (queue->rear+1)%MaxSize==queue->front)
return true;
else return false;
}
int BFS(int grid[][5], int row, int column)
{
int result = 0;
SqQueue queue;
queue.front = queue.rear = 0;
for (int i = 0; i < row; ++i)
{
for (int j = 0; j < column; ++j)
{
if (grid[i][j] == 1&&!isFull(&queue))
{
cout << "进入" << endl;
result += 1;
enQueue(&queue, i, j);
while (!isEmpty(&queue))
{
if (queue.data[queue.front].x - 1>=0&&grid[queue.data[queue.front].x - 1][queue.data[queue.front].y] == 1)
enQueue(&queue, queue.data[queue.front].x - 1, queue.data[queue.front].y);
if (queue.data[queue.front].x + 1<row&& grid[queue.data[queue.front].x + 1][queue.data[queue.front].y] == 1)
enQueue(&queue, queue.data[queue.front].x + 1, queue.data[queue.front].y);
if (queue.data[queue.front].y - 1 >= 0 && grid[queue.data[queue.front].x][queue.data[queue.front].y- 1] == 1)
enQueue(&queue, queue.data[queue.front].x, queue.data[queue.front].y-1);
if (queue.data[queue.front].y+ 1<column && grid[queue.data[queue.front].x][queue.data[queue.front].y + 1] == 1)
enQueue(&queue, queue.data[queue.front].x , queue.data[queue.front].y+1);
deQueue(&queue, grid);
}
}
}
}
return result;
}
int main()
{
int grid[4][5] =
{
1,1,1,1,0,
1,1,0,1,0,
1,1,0,0,0,
0,0,0,0,0,
};
cout << "BFS算法" << BFS(grid, 4, 5);
}