此題的意思就是在用‘
.’和‘
#’組成的圖形中，有多少個長方形。這類問題最容易想到的方法就是
BFS，這題我依然按照這個思路去想。
利用BFS很容易得出有多少個由 # 組成的圖形，問題的關(guān)鍵成為了如何判斷一個圖形是否是長方形。
如下圖形：
. . . .
##. .
##. .
. . . .
一眼即可看出它是個長方形（廢話）。
再看另一個：
. . . .
## . .
### .
. . . .
它不是一個長方形。
如果注意到兩個圖形的行坐標的最大值最小值、列坐標的最大值最小值與圖形的面積之間的關(guān)系，我們很容易想出來一個算法。
(xmax-xmin+1)*(ymax-ymin+1)==area
是一個長方形；
否則不是。
時間復雜度O(rc)，1000*1000的數(shù)據(jù)規(guī)模完全可以承受。
此題還有其他解法。
這種方法很好理解，但是程序有點長，因為涉及到BFS。
Ps：另外說明一下BFS應(yīng)該由一個點出發(fā)向8個點搜索，題目中說的不是太清楚。這一點我也是看了測試數(shù)據(jù)才知道。
以下是我的程序：
#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 閱讀(406)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索