大家有好的代码请发我邮箱：
zhangjia888334@sohu.com 
今天就作了广搜三道题，做个小节。
首先要纠正脑子里的一个错误观念，以前的我的广搜模式就是开个队列，走过的点不能走，队列的类型我还必定是用结构体来做
结构体里放个x,y,n，x-->横坐标，y-->纵坐标，n-->步数
再来几个标准的二维数组，map[Maxh][Maxw]-->描述地图,visit[Maxh][Maxw]--〉描述走没走过.
这都是我以前默认的广搜类型，这三道题我感觉每个都有每个得特色，都有各自特殊情况
首先是第一道：
A:Tom and Jerry这道题就不需要开队列，他每次走都只有一个方向，每次的行走只有一个目标，所以只要有个while(1)的循环
在循环里加上判断可以break的情况
这道题开始我犯了一个错误，我认为他们再次同时到达以前他们同时到达的位置就失败了
但是我没考虑方向，应该是他们同时到达以前他们到达的位置，并且方向还和以前一样，这样才是失败的
但是及便加上这个也是tle
比如争对以下这种数据：(是死都出不来的)
*...*...*C
......*.**
...*...*..
..........
...*......
*.....*...
...*......
..M......*
...*.*....
.*.*......
所以加上了另外一个很恶心的结束条件，以下是我的代码，这道题有个地方的处理不好，内存很大
#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;//当前位置
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的，因为它首先是需要算最少数的题，然后，当我们重新以相同的方向走到以前走过的点时时不需要入队的，所以他的visit是三维的，runtime error了一次，主要是我的queue 开的太小了，我开始只开了Max*Max，但是一个点可能要入队几次，因为有不同的方向，所以只开这么点是不够的，以下是我的代码：
//一碰见能转弯的一定要转
//随便向左向右
//但是不能往后走,或是回转
//到达房间边缘就算是出来了，算最短步数
#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){//到达房间边界
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！这道题我其实做了两层搜索，我代码有点冗长，看别人都很短，不知道他们是怎么实现的
首先解释下我的
int visit[Max][Max][Max][Max];
//cx,cy,mx,my
在每次定位cx,cy（箱子坐标）好时，我们都要设置visit以下，主要是把箱子附近的人可到达位置定为1，这样下次再遍历到就不用加入队列了
这道题我还蛮像写清楚我是怎么想的，但还真有点混乱，尤其是这一段
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的那个搜索，因为这个搜索其实是针对人所能到达位置的搜索
而人有两个地方是到不了的，一个是箱子的地方，一个是障碍物的地方
而箱子这个就要注意了，因为箱子位置是动态的，所以不能通过map[][]是否等于2来判断。
posted on 2008-04-10 00:57
zoyi 阅读(340)
评论(0) 编辑 收藏 引用 所属分类:
acm 、
搜索