Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求In Reply To:请大牛指点,怎么用广搜做这道题啊?为什么的所有数据(包括discuss上的),可还是不能A啊? Posted by:yingyefanxing at 2011-04-07 13:56:51 > #include<iostream> > #include<queue> > using namespace std; > int map[21][21]; > int w,h,res; > int si,sj,ei,ej; > int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};//下右上左 > > struct node > { > int x,y; > int steps; > }; > node pre; > void bfs() > { > queue<node> que; > pre.x=si; > pre.y=sj; > pre.steps=0; > map[pre.x][pre.y]=0; > que.push(pre); > while(!que.empty()) > { > pre=que.front(); > que.pop(); > if(pre.steps>=10) continue; > for(int i=0;i<4;i++) > { > int pi,pj; > pi=pre.x+dir[i][0]; > pj=pre.y+dir[i][1];//前进一步 > bool flog=0; > while(pi>=0&&pi<h&&pj>=0&&pj<w&&map[pi][pj]==0) > { > pi+=dir[i][0]; > pj+=dir[i][1]; > flog=1; > } > if(map[pi][pj]==3) > { > res=pre.steps+1; > return ; > } > if(pi<0||pi>=h||pj<0||pj>=w) continue;//如果越界,则选择其他方向 > if(flog==0) continue;//如果第一步是障碍物,则选择其他方向 > > map[pi][pj]=0; > node p; > p.x=pi-dir[i][0]; > p.y=pj-dir[i][1]; > p.steps=pre.steps+1; > que.push(p); > } > } > } > int main() > { > int i,j; > while(scanf("%d%d",&w,&h)!=EOF&&(w||h)) > { > for(i=0;i<h;i++) > for(j=0;j<w;j++) > { > scanf("%d",&map[i][j]); > if(map[i][j]==2) > si=i,sj=j; > else if(map[i][j]==3) > ei=i,ej=j; > } > res=-1; > bfs(); > printf("%d\n",res); > } > return 0; > } > Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator