> 一开始看到这题    就想到用广度优先搜索      然后使用优先队列    结果行不通    
> 有一组数据通不过  如下 ：
> 10 10
>           
>       X   
>           
>           
>           
>          X
>           
>           
>           
>           
> 7 2 10 6
> 10 6 7 2
> 7 2 10 6
> 0 0 0 0
> 
> 答案应该都是   2 segments的 结果都成了3 segments
> 纠结了好久      初步断定是 vis[][]数组那里的问题
> 
> 
> 奇迹是将它改作普通的队列，竟然AC了       很奇特吧    
> 
> 还有一件事   就是控制方向的那个数组  
> 原来的是  
> int dir[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};/*上下左右*/
>   
> 给WA了  
> 原因还是有一组数据不能通过    如下
> 7 6
> XXXXXXX
> X     X
> X   X X
> X X   X
> X     X
> XXXXXXX
> 1 3 7 4
> 1 4 7 3
> 1 3 3 1
> 1 3 4 1
> 1 3 5 1
> 1 5 7 5
> 3 4 5 3
> 0 0 0 0
> 
> 其中的 pair 3     pair  4  不能通过  
> 
> 然后改成了   
> int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; /*		右左上下 */
> 
> 就给AC了 
> 
> 
> 
> 你说奇不奇特  ！！！！！     小小滴附一下代码  
> 
> 
> 
> #include<iostream>
> #include<cstring>
> #include<queue>
> #include<cstdio>
> using namespace std;
> int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}}; /*		右左上下 */
> char map[77][77];
> bool vis[77][77];
> int x1,y1,x2,y2,w,h;
> struct Node
> {
> 	int x,y,step,dir;   /*	x,y代表方向，step走了几步，dir = （0初始状态，1直走，2横走)*/
> };
> 
> bool  operator <(const Node &a,const Node &b)
> {
> 	return a.step > b.step;
> }
> 
> int  bfs()
> {
> 	memset(vis,0,sizeof(vis));
> 	//	priority_queue<Node>q;  /*   用优先队列就错了   */
> 	queue<Node>q;
> 	Node s,e;
> 	s.x = x1;
> 	s.y = y1;
> 	s.step = 0;
> 	s.dir = 0;
> 	vis[s.x][s.y] = 1;
> 	q.push(s);
> 	while(!q.empty())
> 	{
> 		//s = q.top();
> 		s = q.front();
> 		q.pop();
> 		for(int i=0;i<4;i++)
> 		{
> 			e.x = s.x + dir[i][0];
> 			e.y = s.y + dir[i][1];
> 			if(e.x == s.x)  e.dir = 2;		/*	横	*/
> 			else e.dir = 1;		/*	竖	*/
> 			if(e.x>=0&&e.x<=h+1&&e.y>=0&&e.y<=w+1&&!vis[e.x][e.y])
> 			{
> 				
> 				if(s.dir == 0)		e.step = 1;
> 				else 
> 				{
> 					if(s.dir == e.dir) e.step = s.step;
> 					else e.step = s.step + 1 ;
> 				}
> 				if(e.x == x2&&e.y==y2)		return e.step;
> 				if(map[e.x][e.y] ==' ')  
> 				{		
> 					vis[e.x][e.y] = 1;
> 					q.push(e);
> 				}
> 			}
> 		}
> 		
> 	}
> 	return false;	
> }
> 
> int main()
> {
> 			freopen("cs.txt","r",stdin);
> 	int i,j,cnt=1,Step;
> 	while(cin>>w>>h&&(w||h))
> 	{
> 		memset(map,' ',sizeof(map));
> 		for(i=1;i<=h;i++)       /*		构建地图	*/
> 		{	getchar();
> 		for(j=1;j<=w;j++)
> 			map[i][j] = getchar();
> 		}
> 		printf("Board #%d:\n",cnt++);   /*		printf("Board #%d:\n",cnt++);  */
> 		int count = 1;
> 		while(cin>>y1>>x1>>y2>>x2)
> 		{
> 			if(x1+y1+x2+y2==0) break;
> 			printf("Pair %d: ",count++);   /*		printf("Pair %d: \n",count++);	*/
> 			Step = bfs();
> 			if(!Step)
> 				printf("impossible.\n");
> 			else printf("%d segments.\n",Step);
> 		}
> 		printf("\n");
> 	}
> 	return  0;
> }
> 
> 
> 
> 

你这个骗子