鄙人是用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;
}








 

• Re:眼睛一闭一挣 BFS-TLE ！眼睛一闭再挣 继续TLE！ 进来看看啦 (4830) 200609020331 2009-03-16 21:21:16