初看到這道題一般人的第一個想法基本上就是建圖，找最短路。但一想到這個做法的無論代碼長度還是算法復雜度都實在浪費時間之後，就決定還不如不做了，覺得應該有簡單的做法。
想了下：從外圍四個牆的某一個門進來，走到寶藏，最小走幾個門，實際就是進門點和寶藏的連線goalLine穿過幾個點。
證明不好證，但如果說明大體的思想其實挺簡單的：思想有點像兩點之間直線最短。不要去管縱橫交錯的小線段，只管一開始原始輸入的線段，因為在正方形范圍內，這些線段可以想象為無限長，進門的點和寶藏點中間橫跨著k條直線（牆 ），你就無法繞過它們，只能穿過它們 ，你往左往右走都只會徒增加你要穿過的牆，就這最基本的k道牆你總是要穿過。
就如下簡單示意圖，可以看到從進門點到寶藏，總有3條線你必須穿過。
所以問題就變成了，外圍小線段的中點與寶藏的連線，與內部線的交點個數。
後來我試了下將其變成，外圍小線段的端點與寶藏的連線，與內部線的交點個數，也ac了，但是我感覺這大概是數據比較弱的緣故，推了下感覺好像不行。有哪位兄弟真的認真推導過了，歡迎指正。。
下面的是用端點與寶藏的連線的代碼。。
#include <iostream>
#include <vector>
using namespace std;
class Point
{
public:
Point()
{
x=0.0f;
y=0.0f;
}
Point(double tx,double ty)
{
x=tx;
y=ty;
}
double x,y;
};
class Segment
{
public:
Segment()
{
}
Segment(Point p1,Point p2)
{
point1=p1;
point2=p2;
}
Point point1,point2;
};
//return (p2-p1)*(p3-p1)
double CrossProduct(Point p1,Point p2,Point p3)
{
Point vec1=Point(p2.x-p1.x,p2.y-p1.y);
Point vec2=Point(p3.x-p1.x,p3.y-p1.y);
return (vec1.x*vec2.y - vec1.y*vec2.x );
}
bool SegmentInteract(Segment seg1,Segment seg2)
{
double d1=CrossProduct(seg2.point1,seg2.point2,seg1.point1);
double d2=CrossProduct(seg2.point1,seg2.point2,seg1.point2);
double d3=CrossProduct(seg1.point1,seg1.point2,seg2.point1);
double d4=CrossProduct(seg1.point1,seg1.point2,seg2.point2);
if(d1*d2<0 && d3*d4<0)
return true;
return false;
}
int main()
{
vector<Segment> segVec;
vector<Point> pointVec;
int iSegment;
cin>>iSegment;
double px1,px2,py1,py2;
for(int i=0;i<iSegment;i++)
{
Point p1,p2;
cin>>p1.x>>p1.y>>p2.x>>p2.y;
segVec.push_back(Segment(p1,p2));
pointVec.push_back(p1);
pointVec.push_back(p2);
}
pointVec.push_back(Point(0,0));
pointVec.push_back(Point(0,100));
pointVec.push_back(Point(100,100));
pointVec.push_back(Point(100,0));
Point goalPoint;
cin>>goalPoint.x>>goalPoint.y;
int MinDoorNumber=1<<30;
for(vector<Point>::iterator pointIter=pointVec.begin();pointIter!=pointVec.end();pointIter++)
{
int iInteractNumber=0;
for(vector<Segment>::iterator segIter=segVec.begin();segIter!=segVec.end();segIter++)
{
if(SegmentInteract(Segment(goalPoint,*pointIter),*segIter))
{
iInteractNumber++;
}
}
if(iInteractNumber<MinDoorNumber)
{
MinDoorNumber=iInteractNumber;
}
}
if(MinDoorNumber==1<<30)
MinDoorNumber=0;
cout<<"Number of doors = "<<MinDoorNumber+1<<endl;
return 0;
}
作者：qiul12345
