题目描述：传送门
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
* 第一行: 房间数.
* 第二行: 牛群数.
题目分析：
一道典型的搜索题；
方法一：我们可以先把图中所有的联通块都标记出来，然后再逐个判断当前联通块是否是一个矩形。
判断矩形的方法：我的方法比较暴力~~ 以当前点拓展出这个点最多能到达 上下左右四个位置 然后暴力两重循环判断是否为矩形 ：需要满足在当前区域中没有 '.' 并且在这个区域中没有属于其他联通块的 '#'
为了避免某些奇怪的形状符合上述要求，却并不是一个矩形，所以需要对于每一个被第一遍搜索标记的联通块都check( )一遍，为了让当前这个联通块中的其他方块来更新我整个联通块的合法性
这里为了剪枝，将use[]数组分为3个类型：
1：use[i]=0; 表示当前联通块我还没有搜索到。
2：use[i]=1; 表示目前为止这个联通块是合法的
3：use[i]=-1;表示这个联通块不是合法的，这样的话当枚举判断时遇到use[i]=-1时可以直接跳过
当然，暴力嘛 时间复杂度自然就高 但是数据小2333
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
char s[100];
int n,m,ans;
int a[100][100];
int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};
int book[100][100];
struct your
{
int x,y;
};
void bfs(int x,int y)
{
queue<your>q;
your nmp;
nmp.x=x,nmp.y=y;
q.push(nmp);
book[x][y]=ans;
while(q.size())
{
nmp=q.front();
q.pop();
for(int i=1;i<=4;i++)
{
int dxx=dx[i]+nmp.x;
int dyy=dy[i]+nmp.y;
if(dxx<1||dxx>n||dyy<1||dyy>m)
continue;
if(!book[dxx][dyy]&&a[dxx][dyy])
{
book[dxx][dyy]=ans;
your temp;
temp.x=dxx,temp.y=dyy;
q.push(temp);
}
}
}
}
int tmp;
int use[100];
void check(int x,int y)
{
int dx1=x;int dx2=x;
int dy1=y;int dy2=y;
for(int i=x-1;i>=1;i--)
{
if(!a[i][y])break;
dx1=i;
}
for(int i=x+1;i<=n;i++)
{
if(!a[i][y])break;
dx2=i;
}
for(int i=y-1;i>=1;i--)
{
if(!a[x][i])break;
dy1=i;
}
for(int i=y+1;i<=m;i++)
{
if(!a[x][i])break;
dy2=i;
}
for(int i=dx1;i<=dx2;i++)
for(int j=dy1;j<=dy2;j++)
if(!a[i][j]||(a[i][j]&&(book[i][j]!=book[x][y])))
{
use[book[x][y]]=-1;
break;
}
if(use[book[x][y]]==0)
use[book[x][y]]=1;
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",&s[0]);
for(int j=0;j<m;j++)
if(s[j]=='#')a[i][j+1]=1;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(!book[i][j]&&a[i][j]==1)
ans++,bfs(i,j);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(book[i][j]&&use[book[i][j]]!=-1)
check(i,j);
for(int i=1;i<=ans;i++)
if(use[i]==1)tmp++;
printf("%d\n%d",tmp,ans-tmp);
}方法二：时间复杂度高的原因是在于暴力判断矩形那部分 那么，我们可不可以一边搜索一边判断矩形？答案是肯定的。
据说Tonyzhao是这么做的(DFS) 可以来看一看~~
发完链接就跑路#滑稽
