此题的意思就是在用‘
.’和‘
#’组成的图形中，有多少个长方形。这类问题最容易想到的方法就是
BFS，这题我依然按照这个思路去想。
利用BFS很容易得出有多少个由 # 组成的图形，问题的关键成为了如何判断一个图形是否是长方形。
如下图形：
. . . .
##. .
##. .
. . . .
一眼即可看出它是个长方形（废话）。
再看另一个：
. . . .
## . .
### .
. . . .
它不是一个长方形。
如果注意到两个图形的行坐标的最大值最小值、列坐标的最大值最小值与图形的面积之间的关系，我们很容易想出来一个算法。
(xmax-xmin+1)*(ymax-ymin+1)==area
是一个长方形；
否则不是。
时间复杂度O(rc)，1000*1000的数据规模完全可以承受。
此题还有其他解法。
这种方法很好理解，但是程序有点长，因为涉及到BFS。
Ps：另外说明一下BFS应该由一个点出发向8个点搜索，题目中说的不是太清楚。这一点我也是看了测试数据才知道。
以下是我的程序：
#include<stdio.h>
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
typedef struct
{
long front,rear,count,x[100000],y[100000];
}Queue;
char map[1001][1001];
long r,c;
long id[]={-1,-1,0,1,1,1,0,-1};
long jd[]={0,1,1,1,0,-1,-1,-1};
int used[1001][1001]={0};
void clear(Queue *q)
{
q->count=0;
q->front=0;
q->rear=-1;
}
void put(Queue *q,long a,long b)
{
q->count++;
q->rear++;
q->x[q->rear]=a;
q->y[q->rear]=b;
}
void get(Queue *q,long *a,long *b)
{
q->count--;
*a=q->x[q->front];
*b=q->y[q->front];
q->front++;
}
int empty(Queue *q)
{
return (q->count<=0);
}
long bfs1()
{
long i,j,re=0;
for(i=0;i<r;i++)
for(j=0;j<c;j++)
if(map[i][j]=='#')
re++;
return re;
}
long bfs2(long *ans)
{
long i,j,k,t1,t2,re=0,xmin,xmax,ymin,ymax,flag;
Queue A;
clear(&A);
for(i=0;i<r;i++)
for(j=0;j<c;j++)
{
flag=0;
if(map[i][j]=='#'&&!used[i][j])
{
put(&A,i,j);
xmin=xmax=i;
ymin=ymax=j;
flag=1;
}
while(!empty(&A))
{
get(&A,&t1,&t2);
if(!used[t1][t2])
{
used[t1][t2]=1;
xmin=min(xmin,t1);
xmax=max(xmax,t1);
ymin=min(ymin,t2);
ymax=max(ymax,t2);
for(k=0;k<8;k++)
if(t1+id[k]>=0&&t1+id[k]<r&&t2+jd[k]>=0&&t2+jd[k]<c&&!used[t1+id[k]][t2+jd[k]]&&map[t1+id[k]][t2+jd[k]]=='#')
put(&A,t1+id[k],t2+jd[k]);
}
}
if(flag)
{
re+= (xmax-xmin+1)*(ymax-ymin+1);
(*ans)++;
}
}
return re;
}
int main()
{
FILE *fin,*fout;
fin=fopen("battle.in","r");
long i,j,area1,area2,ans=0;
fscanf(fin,"%ld%ld",&r,&c);
for(i=0;i<r;i++)
fscanf(fin,"%s",map[i]);
fclose(fin);//------Read In
area1=bfs1();
area2=bfs2(&ans);
fout=fopen("battle.out","w");
if(area1!=area2)
fprintf(fout,"Bad placement.\n");
else
fprintf(fout,"There are %ld ships.\n",ans);
fclose(fout);
return 0;
}
posted on 2010-01-06 18:46
lee1r 阅读(361)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：搜索