首页 > 代码库 > 利用DFS求联通块个数
利用DFS求联通块个数
/*572 - Oil Deposits---DFS求联通块个数:从每个@出发遍历它周围的@。每次访问一个格子就给它一个联通编号,在访问之前,先检查他是否---已有编号,从而避免了一个格子重复访问多次--*/#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<string.h>#include<algorithm>using namespace std;const int maxn = 100 + 5;char M[maxn][maxn];int idx[maxn][maxn];int m, n;void dfs(int r, int c, int id){ if (r < 0 || c < 0 || r >= n || c >= m)return; //出界 if (idx[r][c]>0||M[r][c]!=‘@‘)return; //已经访问过,或者不是@ idx[r][c] = id; //该联通分量编号 for (int dr = -1; dr <= 1; dr++){ //扫描它周围的8个方向 for (int dc = -1; dc <= 1; dc++)if (dr || dc) dfs(dr + r, dc + c, id); }}int main(){ while (scanf("%d%d", &n, &m) && m&&n){ for (int i = 0; i < n; i++) scanf("%s", M[i]); int cnt = 0; memset(idx, 0, sizeof(idx)); //没有访问 for (int i = 0; i < n;i++) for (int j = 0; j < m; j++){ //如果当前没有被访问过,并且当前位置字符是@ if (idx[i][j] == 0 && M[i][j] == ‘@‘) dfs(i, j, ++cnt); } printf("%d\n", cnt); } return 0;}
利用DFS求联通块个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。