hiho一下 第156周 岛屿 （dfs）

hiho一下 第156周 岛屿 （dfs）

描述

给你一张某一海域卫星照片，你需要统计：照片中海岛的数目照片中面积不同的海岛数目照片中形状不同的海岛数目其中海域的照片如下，”.”表示海洋，”#”表示陆地。在”上下左右”四个方向上连在一起的一片陆地组成一座岛屿。.####.. .....#. ####.#. .....#. ..##.#.上图所示的照片中一共有4座岛屿；其中3座面积为4，一座面积为2，所以不同面积的岛屿数目是2；有两座形状都是”####”，所以形状不同的岛屿数目为3。

输入

第一行包含两个整数：N 和 M，(1 ≤ N, M ≤ 50)，表示照片的行数和列数。以下一个 N * M 的矩阵，表示表示海域的照片。

输出

输出3个整数，依次是照片中海岛的数目、面积不同的海岛数目和形状不同的海岛数目。

样例输入

5 7.####.......#.####.#......#...##.#.

样例输出

4 2 3

思路

用一个数组标记某个点是否被访问，然后 ​​dfs​​ 遍历整张地图，分别记录每个联通块的内容。

最后输出联通块的数量以及不同的联通块大小，比较某两个联通块形状是否相同可以先把它移动到原点（左上角），然后再比较内容。（毕竟数据很小）

AC 代码

#include #includeusing namespace std;#define INF 0x3f3f3fconst int N = 55;char mapp[N][N];bool isvis[N][N];vectorG[N*N];int minn[N*N];int n,m;int ind;const int mv[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};void dfs(int x,int y){ isvis[x][y]=true; //标记已访问 G[ind].push_back(x*n+y); //记录当前联通块坐标 minn[ind]=min(minn[ind],x*n+y); //当前联通块中的最小坐标 for(int i=0; i<4; i++) //四个方向 { int xi=x+mv[i][0]; int yi=y+mv[i][1]; if(xi<0||xi>=n||yi<0||yi>=m||isvis[xi][yi])continue; //不成立 dfs(xi,yi); }}void solve(){ for(int i=0; i size; set area; for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。