> 鄙人是用BFS做的+保存路径 用总数减去 由里面往边界走的和由外面往里面走的 代码如下 一直TLE 帮我看看 非常谢谢！
> #include<iostream>
> using namespace std;
> #define MAX 2*60000
> 
> int turn[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
> struct Point
> {
> 	int x,y;
> }queue[MAX],pre[6000];
> bool mk[100][100];
> int map[100][100];
> int counts[100][100];
> int x3[100],y3[100];
> bool nod;
> int n,m,cnt;
> 
> int BFS(int x,int y,int x2,int y2)
> {
> 	int front=0,rear=0;
> 	int i;
> 	int a,b;
> 	for(i=0;i<100;i++)
> 	{
> 		x3[i]=-1;
> 		y3[i]=-1;
> 	}
> 	memset(counts,0,sizeof(counts));
> 	mk[x][y]=true;
> 	queue[rear].x=x;
> 	queue[rear].y=y;
> 	rear++;
> 	while(front<rear)
> 	{
> 		x=queue[front].x;
> 		y=queue[front].y;
> 		front++;
> 		for(i=0;i<4;i++)
> 		{
> 			a=x+turn[i][0];
> 			b=y+turn[i][1];
> 			if(!mk[a][b] && map[a][b] && a>=0 && a<=m+1 && b>=0 && b<=n+1)
> 			{
> 				mk[a][b]=true;
>                 x3[a]=x;
> 				y3[b]=y;
> 				counts[a][b]=counts[x][y]+1;
> 				if(a==x2 && b==y2)
> 					return counts[a][b];
> 				queue[rear].x=a;
> 				queue[rear].y=b;
> 				rear++;
> 			}
> 		}
> 	}
> 	return 0;
> }
> 
> int main()
> {
> 	int i,j,count=1;
> 	int x,y,x1,y1,a,b,e,f;
> 	int t1,t2,ant;
> 	bool flag;
> 	char ch;
> 	while(1)
> 	{
> 		scanf("%d%d",&n,&m);
> 		if(n==0 && m==0)
> 			break;
> 		for(i=0;i<=80;i++)
> 			for(j=0;j<=80;j++)
> 				map[i][j]=1;
> 			memset(mk,false,sizeof(mk));
> 			for(i=1;i<=m;i++)
> 			{
> 				getchar();
> 				for(j=1;j<=n;j++)
> 				{
> 					while(scanf("%c",&ch)&& ch!='X' && ch!=' ');
> 					if(ch=='X')
> 						map[i][j]=0;
> 					
> 				}
> 			}
> 			i=1;
> 			flag=true;
> 			while(1)
> 			{
> 				scanf("%d%d%d%d",&x,&y,&x1,&y1);
> 				if(x==0 && y==0 && x1==0 && y1==0)
> 					break;
> 				
> 				nod=false;
> 				cnt=0;
> 				e=x1;
> 				f=y1;
> 				t1=map[y][x];
> 				t2=map[y1][x1];
> 				map[y][x]=1;
> 				map[y1][x1]=1;
> 				if(flag)
> 				{
> 					printf("Board #%d:\n",count);
> 					flag=false;
> 				}
> 				ant=BFS(y,x,y1,x1);
> 				while(x3[f]!=-1 && y3[e]!=-1)
> 				{
> 					a=x3[e];
> 					b=y3[f];
> 					if((e!=0 && e!=m+1 && f!=0 && f!=n+1) && (a==0 || a==m+1 || b==0 || b==n+1))
> 					{
> 						nod=true;
> 						cnt++;
> 					}
> 					e=a;
> 					f=b;
> 				}            
> 				if( ant && !nod)
> 					printf("Pair %d: %d segments.\n",i,counts[y1][x1]-1);
> 				else if(ant && nod)
> 					printf("Pair %d: %d segments.\n",i,counts[y1][x1]-2*cnt-1);
> 				else
> 					printf("Pair %d: impossible.\n",i);
> 				map[y][x]=t1;
> 				map[y1][x1]=t2;
> 				i++;
> 			}
> 			count++;
> 	}
> 	return 0;
> }
> 改后 处理后 WA

> 
> #include<iostream>
using namespace std;
#define MAX 2*60000

int turn[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
struct Point
{
	int x,y;
}queue[MAX],pre[6000];
bool mk[100][100];
int map[100][100];
int counts[100][100];
int n,m;

int BFS(int x,int y,int x2,int y2)
{
	int front=0,rear=0;
	int i;
	int a,b;
	memset(counts,0,sizeof(counts));
	mk[x][y]=true;
	queue[rear].x=x;
	queue[rear].y=y;
	rear++;
	while(front<rear)
	{
		x=queue[front].x;
		y=queue[front].y;
		front++;
		for(i=0;i<4;i++)
		{
			a=x+turn[i][0];
			b=y+turn[i][1];
			if(!mk[a][b] && map[a][b] && a>=0 && a<=m+1 && b>=0 && b<=n+1)
			{
				mk[a][b]=true;
				if((x!=0 && x!=m+1 && y!=0 && y!=n+1 ) && (a==0 || a==m+1 || b==0 || b==n+1))  //由里转向外不计数
                counts[a][b]=counts[x][y]+0;
				else if((x==0 || x==m+1 || y==0 || y==n+1 ) && (a!=0 && a!=m+1 && b!=0 && b!=n+1)) //由外转向里不计数
                counts[a][b]=counts[x][y]+0;
				else
				counts[a][b]=counts[x][y]+1;
				if(a==x2 && b==y2)
					return counts[a][b];
				queue[rear].x=a;
				queue[rear].y=b;
				rear++;
			}
		}
	}
	return 0;
}

int main()
{
	int i,j,count=1;
	int x,y,x1,y1;
	int t1,t2,ant;
	bool flag;
	char ch;
	while(1)
	{
		scanf("%d%d",&n,&m);
		if(n==0 && m==0)
			break;
		for(i=0;i<=80;i++)
			for(j=0;j<=80;j++)
				map[i][j]=1;
			memset(mk,false,sizeof(mk));
			for(i=1;i<=m;i++)
			{
				getchar();
				for(j=1;j<=n;j++)
				{
					while(scanf("%c",&ch)&& ch!='X' && ch!=' ');
					if(ch=='X')
						map[i][j]=0;
					
				}
			}
			i=1;
			flag=true;
			while(1)
			{
				scanf("%d%d%d%d",&x,&y,&x1,&y1);
				if(x==0 && y==0 && x1==0 && y1==0)
					break;	
				t1=map[y][x];
				t2=map[y1][x1];
				map[y][x]=1;
				map[y1][x1]=1;
				if(flag)
				{
					printf("Board #%d:\n",count);
					flag=false;
				}
				ant=BFS(y,x,y1,x1);      
				if(ant)
					printf("Pair %d: %d segments.\n",i,counts[y1][x1]-1);
				else
					printf("Pair %d: impossible.\n",i);
				map[y][x]=t1;
				map[y1][x1]=t2;
				i++;
			}
			count++;
	}
	return 0;
}






> 
> 
> 
> 
> 
>