打算把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;
}
领取专属 10元无门槛券
私享最新 技术干货