【题解】卫星照片 _牛群

题目描述
John正在研究他的农场的卫星照片。照片为一个R（1≤R≤75）行，C（1≤C≤75）列的字符矩阵表示.如下图：
.................. ..#####.......##.. ..#####......##... .................. #.......###.....#. #.....#####.......
图上的一块相连通的“#”表示一群奶牛或一个房间，两个子“#”连通的意思是说左右或上下相连，而下面的两块则是分开的：
.... .#.. ..#. ....
John现在根据卫星照片上的的这些“#”块的形状来判断哪些是牛群，哪些是房间。如果一个“#”块形状的边是水平或垂直的矩形，则是房间。其它的则认为都是牛群。在第一个图中，有三个房间（2×1，2×5和1×1）和2群牛。
请根据输入文件中的数据，统计出房间数和牛群数。
数据中牛群不会包围另一个牛群或房间。
输入输出格式输入格式
第一行，两个整数：R和C；

文章插图
第二至R+1行，第i+1行表示照片的第i行情况，由C个字符组成。
输出格式
第一行，一个整数，为房间数。
第二行，一个整数，为牛群数。
输入输出样例
输入样例
5 8
#####..#
#####.##
......#.
.###...#
.###..##
输出样例
2
2
题解
搜索时记录连通块的左上角、左下角、右上角、右下角，如果以此得出的矩形面积与连通块的面积相等，这个连通块就是矩形。
#include #include //#include using namespace std;int r,c;int a[77][77];int num;int minx,maxx,miny,maxy;int room,cow;int cnt;struct node{int x,y;}b[75*75+2];bool cmp(node a,node b){if(a.x!=b.x) return a.x>r>>c;char temp;//temp='#';for(int i=1;i<=r;i++){for(int j=1;j<=c;j++){cin>>temp;if(temp=='#'){a[i][j]=1;b[++cnt].x=i;b[cnt].y=j;}}}sort(b+1,b+1+cnt,cmp);f();if(cnt>1) dfs(b[1].x,b[1].y,b[1].x,b[1].y);else if(cnt) room++;cout<
【【题解】卫星照片】参考程序