网站建设年终总结,nginx 运行wordpress,百度短链接生成网址,网站 技术支持目录题目代码#xff08;Flood Fill#xff09;代码#xff08;并查集#xff09;题目 题目链接
找出房间个数——求连通块个数 最大房间——求最大连通块
直接用flood fill算法
注意题目的输入#xff0c;例如118211182111821#xff0c;则代表有西、北、南墙…
目录题目代码Flood Fill代码并查集题目 题目链接
找出房间个数——求连通块个数 最大房间——求最大连通块
直接用flood fill算法
注意题目的输入例如118211182111821则代表有西、北、南墙
代码Flood Fill
上下左右的走向可以预先设置数组dx[4] {0, -1, 0, 1}, dy[4] {-1, 0, 1, 0}; 墙的表示相当于二进制编码可以用位运算获取特定位的数值(p[t.x][t.y] i 1
#include iostream
#define x first
#define y second
using namespace std;int n, m;
int p[55][55];
bool st[55][55];
typedef pairint, int PII;
PII q[2505];int bfs(int i, int j) {int hh 0, tt 0;int dx[4] {0, -1, 0, 1}, dy[4] {-1, 0, 1, 0};q[0] {i, j};st[i][j] true;while(hh tt) {PII t q[hh ];for (int i 0; i 4; i ) {int tx t.x dx[i], ty t.y dy[i];if (tx 0 || tx m || ty 0 || ty n) continue; // 越界 if (st[tx][ty]) continue; // 已经走过 if ((p[t.x][t.y] i) 1) continue; // 是墙 q[ tt ] {tx, ty}; // 入队 st[tx][ty] true;}}return tt 1; // 队列同时有的元素个数就是连通块大小
}int main () {scanf(%d%d, m, n);for (int i 0; i m; i ) {for (int j 0; j n; j ) {scanf(%d, p[i][j]);} }int max_s 0, cnt 0;for (int i 0; i m; i ) {for (int j 0; j n; j ) {if (st[i][j]) continue;max_s max(max_s, bfs(i, j));cnt ;} }printf(%d\n%d\n, cnt, max_s);return 0;
}
代码并查集
将房间连通也可用并查集枚举每个房间和两个方向东、南西、北西、南东、北皆可如果没墙则连通集合总数-1集合元素个数相加。 注意集合元素个数初始都是1ares初始也为1因为连通块最小也有1个房间
#include iostream
using namespace std;int m, n;
int g[55][55];
const int dx[2] {1, 0}, dy[2] {0, 1}; // 向南、向东
const int dw[2] {8, 4}; // 南墙、东墙int p[2505], np[2505];
int find(int x) {if (p[x] ! x) p[x] find(p[x]);return p[x];
}
int main() {scanf(%d%d, m, n);for (int i 0; i m; i ) {for (int j 0; j n; j ) {scanf(%d, g[i][j]);}}for (int i 0; i m * n; i ) p[i] i, np[i] 1;int cnt m * n, ares 1;for (int i 0; i m; i ) {for (int j 0; j n; j ) {for (int k 0; k 2; k ) {int tx i dx[k], ty j dy[k];if (tx m || ty n) continue; if (g[i][j] dw[k]) continue; // 是墙 int a find(i * n j), b find(tx * n ty); // 找到{i,j}和{tx,ty}的祖先 if (a ! b) {p[a] b; // a合并到b cnt -- ; // 集合总数-1 np[b] np[a]; // a元素加到b ares max(ares, np[b]);}}}}printf(%d\n%d\n, cnt, ares);return 0;
}
