Graph Algorithms：Breadth First Search

打算把https://www.geeksforgeeks.org/top-algorithms-and-data-structures-for-competitive-programming/ 复习一遍，今天是第一章，主要是讲图论算法。

https://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

例题 https://practice.geeksforgeeks.org/problems/x-total-shapes/0

这个题目比较简单，不知道为什么设计成了hard，就是求一个图里面的联通子图的数目，具体的就是从一个没有被touch过的点出发，一路上把联通的并且是1的点都染上色，有个cv里头常用的算法，就叫做flood fill吧，不过其实具体实现也就是bfs或者dfs。

#include

#include

#include

using namespace std;

int matrix[50][50];

int direct[4][2] = { {-1, 0}, , , };

typedef struct node {

int i;

int j;

} Node;

bool inbond(int i, int j, int row, int col) {

if (i = row) return false;

if (j = col) return false;

return true;

}

void bfs(int i, int j, int row, int col, int count) {

Node q[50*50];

Node node;

node.i = i;

node.j = j;

q[0] = node;

int bg = 0;

int ed = 0;

while(bg

Node cur = q[bg];

for (size_t di = 0; di

int newi = cur.i + direct[di][0];

int newj = cur.j + direct[di][1];

if (inbond(newi, newj, row, col) && matrix[newi][newj] == 1) {

Node nd;

nd.i = newi;

nd.j = newj;

q[++ed] = nd;

matrix[newi][newj] = count;

}

}

bg++;

}

}

int main() {

//code

int num;

cin >> num;

for (size_t i = 0; i

int row,col;

cin >> row >> col;

for (size_t j = 0; j

string str;

cin >> str;

for (size_t k = 0; k

if (str[k] == 'X')

matrix[j][k] = 1;

else

matrix[j][k] = 0;

}

}

int count = 1;

for (size_t j = 0; j

for (size_t k = 0; k

if (matrix[j][k] == 1)

{

bfs(j, k, row, col, ++count);

}

cout

}

return 0;

}