這是一道不能再簡(jiǎn)單的題目了，我的做法是bfs，其實(shí)這題可以bfs可以dfs，隨便，看愛(ài)好了（floodfill其實(shí)和bfs差不多）。
這道題雖然很簡(jiǎn)單，但很慚愧，我交了很多次……
第一次，低級(jí)錯(cuò)誤，把一次bfs放在內(nèi)層循環(huán)外面了~！
第二次，第十個(gè)數(shù)據(jù)WA；
第三次，忘記把用來(lái)調(diào)試的代碼刪掉，超囧~！
第四次，把第三次的代碼上面的部分代碼刪掉，AC。
但是我其中還是犯了一個(gè)不小的錯(cuò)誤，雖然僥幸AC了。我用used[i][j]把每次出隊(duì)的點(diǎn)標(biāo)記，但是這樣有了重復(fù)現(xiàn)象，我開(kāi)了一個(gè)10000的隊(duì)列結(jié)果內(nèi)存不夠用。后來(lái)改正了一下，不使用used[i][j]=0或1，而是把入隊(duì)的點(diǎn)從“#”改為“-”，這樣一來(lái)在條件中判斷一下就可以避免重復(fù)了。
感覺(jué)這個(gè)錯(cuò)誤也挺低級(jí)，以前bfs的時(shí)候都沒(méi)有這個(gè)錯(cuò)誤……唉，搜索還是需要加強(qiáng)啊。
不過(guò)這個(gè)錯(cuò)誤也對(duì)我有了一個(gè)提醒，在競(jìng)賽內(nèi)存允許的情況下多開(kāi)內(nèi)存還是可以避免一些不必要的錯(cuò)誤的，比如這題，開(kāi)60000的隊(duì)列，我的錯(cuò)誤方法完全沒(méi)有問(wèn)題。
不多說(shuō)，現(xiàn)在練習(xí)中出的錯(cuò)也是一種積累吧。
給出代碼，自然沒(méi)有dfs簡(jiǎn)短了。
#include<stdio.h>
#define size 10000
struct
{
long x[size],y[size],front,rear,count;
}q;
void clear()
{
q.count=0;
q.front=0;
q.rear=-1;
}
void put(long a,long b)
{
q.count++;
q.rear++;
q.x[q.rear]=a;
q.y[q.rear]=b;
}
void get(long *a,long *b)
{
q.count--;
*a=q.x[q.front];
*b=q.y[q.front];
q.front++;
}
int empty()
{
return (q.count==0);
}
int main()
{
clear();
long n,m,i,j,k,t1,t2,ans,sign;
long xd[]={-1,-1,0,1,1,1,0,-1,-2,0,2,0};
long yd[]={0,1,1,1,0,-1,-1,-1,0,2,0,-2};
char map[101][101]={0};
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
{
scanf("\n");
for(j=1;j<=m;j++)
scanf("%c",&map[i][j]);
}
ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j]=='#')
{
put(i,j);
map[i][j]='-';
while(!empty())
{
get(&t1,&t2);
for(k=0;k<12;k++)
if(t1+xd[k]>=1&&t1+xd[k]<=n&&t2+xd[k]>=1&&t2+xd[k]<=m&&map[t1+xd[k]][t2+yd[k]]=='#')
{
put(t1+xd[k],t2+yd[k]);
map[t1+xd[k]][t2+yd[k]]='-';
}
}
ans++;
}
printf("%ld\n",ans);
getchar();getchar();
return 0;
}
posted on 2010-01-06 19:34
lee1r 閱讀(526)
評(píng)論(1) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：搜索