我有两点不是很明确。
1，失败可以直接判断，是不是正确？
由于spiderman的高度在运行的过程中是个常值h，则对于每一高为hh，坐标为x的建筑物，
spiderman可以通过该建筑物运行的起点必须在[x-sqrt（hh*hh - (hh-h)*(hh-h) ）, x).
相应的终点为(x, x+sqrt（hh*hh - (hh-h)*(hh-h) ）]
当然第一个建筑物除外。
所以，spiderman想从起点运行到终点，必须不同建筑物的终点和起点有交点。如果出现下面的情况则失败：
    | 
|---|-----   --|--  
中间的空格，spiderman是不能过去的。

2，确保可以成功，利用广搜求最小次数，会不会太慢？

下面是我TLE的代码，各位大大帮我看看吧^0^

#include<iostream>
//#include<fstream>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

int main(){
	//ifstream cin("spiderman.txt");
    int i;
	int n;
	cin>>n;
	while(n--){

       int m;
	   cin>>m;
	   vector<double> Bc(m,0);
	   vector<double> Bl(m,0);
	   vector<double> Br(m,0);

	   double h,th,tth;
	   double x;
	   double ll,lr;
	   cin>>x>>h;
	   Bc[0]=x;
	   ll=lr=x;
	   for(i=1;i<m;++i){
			cin>>x>>th;
			tth=th-h;
			th=sqrt(th*th-tth*tth);
			Bl[i]=x-th;
			if(Bl[i]<Bc[0]){
				Bl[i]=Bc[0];
				th=x-Bc[0];
			}
			Bc[i]=x;
			Br[i]=x+th;
			//if(Bl[i]<ll)ll=Bl[i];
			if(Bl[i]<=lr&&Br[i]>lr)lr=Br[i];
	   }//end of read in
	   //cout<<ll<<" "<<lr<<endl;
	   if(ll==lr||lr<Bc[m-1])
		   cout<<"-1"<<endl;
	   else{		   
	   
	   
		queue<double> X;
		queue<char>   step;
		queue<char>   S;

		X.push(Bc[0]);step.push(0);S.push(0);
		while(!X.empty()){
			double xc=X.front();X.pop();
			char   sc=step.front();step.pop();
			char   nc=S.front();S.pop();
			
			for(i=nc+1;i<m;++i)
				if(Bl[i]<=xc&&Bc[i]>xc){
					X.push(2*Bc[i]-xc);
					step.push(sc+1);
					S.push(i);
				}

			if(X.back()>=Bc[m-1]){
				cout<<sc+1<<endl;
				break;
			}	
		}
	   }
	}
	return 0;
}

• Re:失败的情况马上就可以判断出来，成功用广搜，但是TLE！ (59) Jin_j_y 2004-10-17 22:56:39
• Re:失败的情况马上就可以判断出来，成功用广搜，但是TLE！ (22) Ivan 2004-10-17 23:52:04
  • Re:失败的情况马上就可以判断出来，成功用广搜，但是TLE！ (104) Jin_j_y 2004-10-18 10:49:16