P5153: 卫星照片-训练套题T2T1
【题目描述】
1. 卫星照片[satel.pas/ c/cpp] 【问题描述】 农夫 John 正在研究他的农场的卫星照片.照片为一个R (1 <=R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图: .................. ..#####.......##.. ..#####......##... .................. #.......###.....#. #.....#####....... 图上的一块相连通的 "#" 表示一群奶牛或一个房间, 两个子"#" 连通的意思是说左右或上下相连.而下面的两块则是分开的: .... .#.. ..#. .... John现在根据卫星照片上的的这些"#"块的形状来判断哪些是牛群,哪些是房间.如果一个"#"块形状的边是水平或垂直的矩形,则是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛. 请根据输入文件中的数据,统计出房间数和牛群数. 数据中牛群不会包围另一个牛群或房间. 【输入数据】 * 第一行,两个整数: R 和 C. * 和 2..R+1行: 第 i+1 行表示照片的第 i 行情况,由 C 字符组成. 【输出数据】 * 第一行: 房间数. * 第二行: 牛群数. 【输入样例】 5 8 #####..# #####.## ......#. .###...# .###..## 【输出样例】 2 2 【数据规模】【提示】
n 照片为一个R (1 <= R <= 75) 行 C (1 <= C <= 75) 列的字符矩阵表示.如下图:
n 如果一个"#"块形状的边是水平或垂直的矩形,则是房间.其它的则认为都是牛群.在第一个图中,有三个房间 ( 2x1, 2x5, and 1x1)和2群牛.
n 请根据输入文件中的数据,统计出房间数和牛群数.
n 数据中牛群不会包围另一个牛群或房间.
n 连通块判断：方格<=75*75个点，用DFS或BFS都可。
n 连通块是否房间判断：
1）左上角(X1,Y1)
2）右下角(X2,Y2)
3）数量 = (X2-X1+1)* (Y2-Y1+1)
n #include <stdio.h>
n int Y,X , nbarn,ncow, minx,maxx,miny,maxy,siz;
n char m[100][100];
n void go (int y, int x);
n void search();
n int main () {
n FILE *in = fopen ("satel.in","rt"); fscanf (in,"%i %i\n",&Y,&X);
n for (int y=0; y<Y; y++) fgets(m[y],100,in); fclose (in);
n search();
n FILE *out = fopen ("satel.out","wt");
n fprintf (out,"%i\n%i\n",nbarn,ncow); fclose (out);
n return 0;
n }
n void search() {
n for (int y=0; y<Y; y++)
n for (int x=0; x<X; x++)
n if (m[y][x]=='#') {
n miny=maxy=y; minx=maxx=x;
n siz=0;
n go(y,x);
n if ((maxx-minx+1)*(maxy-miny+1) == siz)
n nbarn++;
n else
n ncow++;
n }
n void go (int y, int x) {
n if (y<0 || y>=Y || x<0 || x>=X) return;
n if (m[y][x] != '#') return;
n m[y][x]='.';
n siz++;
n miny<?=y;
n maxy>?=y;
n minx<?=x;
n maxx>?=x;
n go(y,x-1);
n go(y,x+1);
n go(y-1,x);
n go(y+1,x);
n }