外贸网站建设公司青岛,网络广告策划的流程顺序为,全国网站开发赛,哈尔滨建工建设/*1. 图也有DFS遍历和BFS遍历#xff0c;前者用递归实现#xff0c;后者用队列实现。由于DFS更容易编写#xff0c;一般用DFS求连通块。求多维数组连通块的过程也称为种子填充2. 一般要尽量避免同一个格子被访问了两次#xff0c;但是在这道题中#xff0c;即便访问两次前者用递归实现后者用队列实现。由于DFS更容易编写一般用DFS求连通块。求多维数组连通块的过程也称为种子填充2. 一般要尽量避免同一个格子被访问了两次但是在这道题中即便访问两次也不会影响最终结果所以横纵坐标变化量取不取 0 0 这组数据都没有关系3. 对于某一点遍历其上下左右对角线时可以写8个dfs递归表示8个方向也可以用两层循环或者用数组记录横纵变化量循环数组下标
*/ #include cstdio
#include cstring
const int maxn 100 5;char pic[maxn][maxn];
int m, n, idx[maxn][maxn];
const int dx[] {-1, -1, -1, 0, 0, 0, 1, 1, 1};
const int dy[] {-1, 0, 1, 0, -1, 1, 0, -1, 1};
//注意对角线也行所以是9种变化 void dfs (int r, int c, int id)
{if (r 0 || r m || c 0 || c n) return; //出界的格子if (idx[r][c] 0 || pic[r][c] ! ) return; //确保格子中是且还没有被访问过idx[r][c] id; //连通分量编号for (int i 0; i 9; i)if (i ! 3) dfs(r dx[i], c dy[i], id); // 行列增量为 0,0的那组数据不管加不加入dfs都不会影响结果因为它被第二次遍历时是不满足 cnt的条件的/* for (int dr -1; dr 1; dr)for (int dc -1; dc 1; dc)
// if (dr || dc) dfs(rdr, cdc, id); // 行列增量为 0,0的那组数据不管加不加入dfs都不会影响结果*/}int main()
{while (scanf(%d%d, m, n) 2 m n){for (int i 0; i m; i)scanf(%s, pic[i]);memset(idx, 0, sizeof(idx));int cnt 0;for (int i 0; i m; i)for (int j 0; j n; j)if (idx[i][j] 0 pic[i][j] ) dfs(i, j, cnt);printf(%d\n, cnt);}return 0;
} 转载于:https://www.cnblogs.com/mofushaohua/p/7789402.html
