Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:请大牛指点,怎么用广搜做这道题啊?为什么的所有数据(包括discuss上的),可还是不能A啊?

Posted by liqiang5689 at 2011-07-28 14:06:42 on Problem 3009
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator