jzoj. 1300. 卫星照片

Description

　　农夫 John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图:
　　………………
　　..#####…….##..
　　..#####……##…
　　………………
　　#…….###…..#.
　　#…..#####…….

　　图上的一块相连通的 “#” 表示一群奶牛或一个房间, 两个子”#” 连通的意思是说左右或上下相连.而下面的两块则是分开的:
　　….
　　.#..
　　..#.
　　….

　　John现在根据卫星照片上的的这些”#”块的形状来判断哪些是牛群,哪些是房间.如果一个”#”块形状一个内部和边全部都是“#”的矩形,则是房间，如果一个连通块只有一个“#”,也是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛.
　　请根据输入文件中的数据,统计出房间数和牛群数.数据中牛群不会包围另一个牛群或房间.

Input

　　* 第一行,两个整数: R 和 C.
　　* 和 2..R+1行: 第 i+1 行表示照片的第 i 行情况,由 C 字符组成.

Output

　　* 第一行: 房间数.
　　* 第二行: 牛群数.

Sample Input

5 8
#####..#
#####.##
......#.
.###...#
.###..##

Sample Output

2
2

分析：bfs暴力枚举每个由#形成的块。
记录你到过的横坐标最小的Minx和最大的maxx;以及最小的纵坐标miny以及最大的纵坐标maxy;
然后记录这个连通块内的格子数目；
然后看一下minxminy以及maxxmaxy对应的矩形应该有的格子数目;如果相等，那么连通块为矩形；否则不是矩形。

代码：

constdx:array [1..4] of longint=(1,0,-1,0);dy:array [1..4] of longint=(0,1,0,-1);
varv:array [1..75,1..75] of boolean;list:array [1..75*75,1..2] of longint;n,m,i,j,ans1,ans2,h,t,maxx,maxy,minx,miny:longint;ch:char;procedure bfs(xx,yy:longint);var i,x,y,sum,x1,y1:longint;
begint:=1; h:=0;list[t,1]:=xx;list[t,2]:=yy;v[xx,yy]:=true;sum:=1;repeatinc(h);x:=list[h,1];y:=list[h,2];for i:=1 to 4 dobeginx1:=x+dx[i];y1:=y+dy[i];if (x1>0) and (y1>0) and (x1<=n) and (y1<=m) thenbeginif v[x1,y1]=false thenbegininc(t);v[x1,y1]:=true;list[t,1]:=x1;list[t,2]:=y1;inc(sum);if x1>maxx then maxx:=x1;if x1then minx:=x1;if y1>maxy then maxy:=y1;if y1then miny:=y1;end;end;end;until h=t;if (maxx-minx+1)*(maxy-miny+1)=sum then inc(ans1)else inc(ans2);
end;beginreadln(n,m);for i:=1 to n dobeginfor j:=1 to m dobeginread(ch);if ch='#' then v[i,j]:=falseelse v[i,j]:=true;end;readln;end;for i:=1 to n dofor j:=1 to m doif v[i,j]=false thenbeginmaxx:=i; minx:=i;maxy:=j; miny:=j;bfs(i,j);end;writeln(ans1);writeln(ans2);
end.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！