3598: 卫星照片-训练套题T2T1

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       }