大家有好的代碼請發(fā)我郵箱：
zhangjia888334@sohu.com 
今天就作了廣搜三道題，做個小節(jié)。
首先要糾正腦子里的一個錯誤觀念，以前的我的廣搜模式就是開個隊列，走過的點(diǎn)不能走，隊列的類型我還必定是用結(jié)構(gòu)體來做
結(jié)構(gòu)體里放個x,y,n，x-->橫坐標(biāo)，y-->縱坐標(biāo)，n-->步數(shù)
再來幾個標(biāo)準(zhǔn)的二維數(shù)組，map[Maxh][Maxw]-->描述地圖,visit[Maxh][Maxw]--〉描述走沒走過.
這都是我以前默認(rèn)的廣搜類型，這三道題我感覺每個都有每個得特色，都有各自特殊情況
首先是第一道：
A:Tom and Jerry這道題就不需要開隊列，他每次走都只有一個方向，每次的行走只有一個目標(biāo)，所以只要有個while(1)的循環(huán)
在循環(huán)里加上判斷可以break的情況
這道題開始我犯了一個錯誤，我認(rèn)為他們再次同時到達(dá)以前他們同時到達(dá)的位置就失敗了
但是我沒考慮方向，應(yīng)該是他們同時到達(dá)以前他們到達(dá)的位置，并且方向還和以前一樣，這樣才是失敗的
但是及便加上這個也是tle
比如爭對以下這種數(shù)據(jù)：(是死都出不來的)
*...*...*C
......*.**
...*...*..
..........
...*......
*.....*...
...*......
..M......*
...*.*....
.*.*......
所以加上了另外一個很惡心的結(jié)束條件，以下是我的代碼，這道題有個地方的處理不好，內(nèi)存很大
#include<iostream>
#define MaxN 10
#define Max 400000
int map[MaxN][MaxN];//1表示能走，0表示不能走
int hash[Max];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int time,mx,my,cx,cy;//當(dāng)前位置
int mdir,cdir;//方向
void solve()
{
int k;
int tmp_cx,tmp_cy,tmp_mx,tmp_my;
while(1){
if(mx==cx&&my==cy){
printf("%d\n",time);
return;
}
k=cy+cx*10+my*100+mx*1000+cdir*10000+mdir*100000;
if(time>1000||hash[k]){
printf("-1\n");
return;
}
tmp_cx=cx+dx[cdir];
tmp_cy=cy+dy[cdir];
tmp_mx=mx+dx[mdir];
tmp_my=my+dy[mdir];
if(tmp_cx<0||tmp_cx>=MaxN||tmp_cy<0||tmp_cy>=MaxN)
cdir=(cdir+1)%4;
else if(map[tmp_cx][tmp_cy]){
cx=tmp_cx;
cy=tmp_cy;
}
else cdir=(cdir+1)%4;
if(tmp_mx<0||tmp_mx>=MaxN||tmp_my<0||tmp_my>=MaxN)
mdir=(mdir+1)%4;
else if(map[tmp_mx][tmp_my]){
mx=tmp_mx;
my=tmp_my;
}
else mdir=(mdir+1)%4;
time++;
}
}
int main()
{
int T,i,j;
char c[20];
while(scanf("%d",&T)!=EOF&&T){
while(T--){
cdir=mdir=time=0;
memset(map,0,sizeof(map));
memset(hash,0,sizeof(hash));
for(i=0;i<MaxN;i++){
scanf("%s",c);
for(j=0;j<MaxN;j++){
if(c[j]!='*')map[i][j]=1;
if(c[j]=='C'){cx=i;cy=j;}
if(c[j]=='M'){mx=i;my=j;}
}
}
solve();
}
}
return 0;
}
這道題我過的還算順利，這道題是需要開queue的，因為它首先是需要算最少數(shù)的題，然后，當(dāng)我們重新以相同的方向走到以前走過的點(diǎn)時時不需要入隊的，所以他的visit是三維的，runtime error了一次，主要是我的queue 開的太小了，我開始只開了Max*Max，但是一個點(diǎn)可能要入隊幾次，因為有不同的方向，所以只開這么點(diǎn)是不夠的，以下是我的代碼：
//一碰見能轉(zhuǎn)彎的一定要轉(zhuǎn)
//隨便向左向右
//但是不能往后走,或是回轉(zhuǎn)
//到達(dá)房間邊緣就算是出來了，算最短步數(shù)
#include<iostream>
#define Max 80
struct node{
int x,y,time,dir;
} queue[100000];
int map[Max][Max];//1表示能走0表示不能
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int visit[Max][Max][4];//x,y,dir
int h,w;
int sx,sy;//起始位置
int head,tail;
void solve()
{
int i,hx,hy,ht,hd;
int px,py,d;
int m,n;
head=tail=0;
for(i=0;i<4;i++){
queue[tail].x=sx;
queue[tail].y=sy;
queue[tail].dir=i;
queue[tail++].time=0;
visit[sx][sy][i]=1;
}
while(head<tail){
m=n=0;
hx=queue[head].x;
hy=queue[head].y;
ht=queue[head].time;
hd=queue[head++].dir;
if(hx==0||hx==h-1||hy==0||hy==w-1){//到達(dá)房間邊界
printf("%d\n",ht);
return;
}
d=(hd+1)%4;//向右走
px=hx+dx[d];py=hy+dy[d];//px,py不會越界，因為hx,hy不在邊界上，再走一步也不會越界
if(map[px][py]){
m=1;
if(!visit[px][py][d]){
queue[tail].x=px;
queue[tail].y=py;
queue[tail].time=ht+1;
queue[tail++].dir=d;
visit[px][py][d]=1;}
}
d=(hd+3)%4;
px=hx+dx[d];py=hy+dy[d];//同樣不會越界
if(map[px][py]){
n=1;
if(!visit[px][py][d]){
queue[tail].x=px;
queue[tail].y=py;
queue[tail].time=ht+1;
queue[tail++].dir=d;
visit[px][py][d]=1;}
}
px=hx+dx[hd];py=hy+dy[hd];
if(!m&&!n&&map[px][py]&&!visit[px][py][hd]){
queue[tail].x=px;
queue[tail].y=py;
queue[tail].time=ht+1;
queue[tail++].dir=hd;
visit[px][py][hd]=1;
}
}
printf("-1\n");
}
int main()
{
int T,i,j;
char c[100];
scanf("%d",&T);
while(T--){
memset(map,0,sizeof(map));
memset(visit,0,sizeof(visit));
memset(queue,0,sizeof(queue));
scanf("%d%d",&h,&w);
for(i=0;i<h;i++){
scanf("%s",c);
for(j=0;j<w;j++){
if(c[j]!='#')map[i][j]=1;
if(c[j]=='@'){sx=i;sy=j;}
}
}
solve();
}
return 0;
}
C Push！這道題我其實做了兩層搜索，我代碼有點(diǎn)冗長，看別人都很短，不知道他們是怎么實現(xiàn)的
首先解釋下我的
int visit[Max][Max][Max][Max];
//cx,cy,mx,my
在每次定位cx,cy（箱子坐標(biāo)）好時，我們都要設(shè)置visit以下，主要是把箱子附近的人可到達(dá)位置定為1，這樣下次再遍歷到就不用加入隊列了
這道題我還蠻像寫清楚我是怎么想的，但還真有點(diǎn)混亂，尤其是這一段
for(i=0;i<4;i++){
pcx=hcx+dx[i]; pcy=hcy+dy[i];
pmx=hcx+dx[(i+2)%4]; pmy=hcy+dy[(i+2)%4];
if(pmx<0||pmx>=h||pcx<0||pcy>=w)continue;
if(pcx<0||pcx>=h||pcy<0||pcy>=w)continue;
if(map[pcx][pcy]==1)continue;
if(visit[pcx][pcy][hcx][hcy])continue;
if(!visit[hcx][hcy][pmx][pmy])continue;
push(hcx,hcy,pcx,pcy,hnum+1);
set_visit(hcx,hcy,pcx,pcy);
}
這兩個visit[][][]的判斷是兩層visit的判斷，要想清楚
這道題基本上寫完后沒什么錯，都是些什么x寫成y，p寫成q的錯誤，這還多虧了pc，我邊聊天，邊寫的
以下是我的代碼：
#include<iostream>
#define Max 7
struct node{
int cx,cy,mx,my,num;
}queue[1000];
int visit[Max][Max][Max][Max];
//cx,cy,mx,my
int map[Max][Max];
//對于人來說邊界不能走，不能走，也不能，其余的可以
//對于箱子來說表示不能走邊界不能走,其余的都能走
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int man_x,man_y,cargo_x,cargo_y;
int w,h;
int head,tail;
void push(int x1,int y1,int x2,int y2,int n)
{
queue[tail].mx=x1;
queue[tail].my=y1;
queue[tail].cx=x2;
queue[tail].cy=y2;
queue[tail++].num=n;
}
void set_visit(int x1,int y1,int x2,int y2)
{//men:(x1,y1),cargo:(x2,y2)
int qnx[1000]={0},qny[1000]={0};
int p,q,px,qy,i;
int fis=0,end=0;
qnx[end]=x1; qny[end++]=y1;
visit[x2][y2][x1][y1]=1;
while(fis<end){
p=qnx[fis]; q=qny[fis++];
for(i=0;i<4;i++){
px=p+dx[i]; qy=q+dy[i];
if(px<0||px>=h||qy<0||qy>=w)continue;
if(map[px][qy]==1)continue;
if(px==x2&&qy==y2)continue;//注意
if(visit[x2][y2][px][qy])continue;
qnx[end]=px; qny[end++]=qy;
visit[x2][y2][px][qy]=1;
}
}
}
void solve()
{
int i;
int hmx,hmy,hcx,hcy,hnum;
int pcx,pcy,pmx,pmy;
push(man_x,man_y,cargo_x,cargo_y,0);
set_visit(man_x,man_y,cargo_x,cargo_y);
while(head<tail){
hmx=queue[head].mx;
hmy=queue[head].my;
hcx=queue[head].cx;
hcy=queue[head].cy;
hnum=queue[head++].num;
if(map[hcx][hcy]==3){
printf("%d\n",hnum);
return;
}
for(i=0;i<4;i++){
pcx=hcx+dx[i]; pcy=hcy+dy[i];
pmx=hcx+dx[(i+2)%4]; pmy=hcy+dy[(i+2)%4];
if(pmx<0||pmx>=h||pcx<0||pcy>=w)continue;
if(pcx<0||pcx>=h||pcy<0||pcy>=w)continue;
if(map[pcx][pcy]==1)continue;
if(visit[pcx][pcy][hcx][hcy])continue;
if(!visit[hcx][hcy][pmx][pmy])continue;
push(hcx,hcy,pcx,pcy,hnum+1);
set_visit(hcx,hcy,pcx,pcy);
}
}
printf("-1\n");
}
int main()
{
int i,j;
while(scanf("%d%d",&w,&h)!=EOF&&w&&h){
head=tail=0;
memset(map,0,sizeof(map));
memset(queue,0,sizeof(queue));
memset(visit,0,sizeof(visit));
for(i=0;i<h;i++)
for(j=0;j<w;j++){
scanf("%d",&map[i][j]);
if(map[i][j]==2){cargo_x=i;cargo_y=j;}
else if(map[i][j]==4){man_x=i;man_y=j;}
}
solve();
}
return 0;
}
ps: 我想到了個push我犯了個錯誤，就是set_visit的那個搜索，因為這個搜索其實是針對人所能到達(dá)位置的搜索
而人有兩個地方是到不了的，一個是箱子的地方，一個是障礙物的地方
而箱子這個就要注意了，因為箱子位置是動態(tài)的，所以不能通過map[][]是否等于2來判斷。
posted on 2008-04-10 00:57
zoyi 閱讀(363)
評論(0) 編輯 收藏 引用 所屬分類:
acm 、
搜索