一开始看到这题    就想到用广度优先搜索      然后使用优先队列    结果行不通    
有一组数据通不过  如下 ：
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;
}

• Re:勉强AC吧 附代码（bfs ） (2871) tenglehan20021205 2015-04-25 16:52:19
• Re:勉强AC吧 附代码（bfs ） (2878) tenglehan20021205 2015-04-25 16:53:26