地图上有一些beeper,让你从起点搜集所有beeper,再回到起点。但你只可以水平或者竖直的走,不能走对角线。让你找出这样走的最短路径长度。
因为地图最大只有20×20,而beeper最多也只有10个,所以可以考虑用深搜,找到所有可能路径,在其中加一些简单的减枝就可以了。起初以为会超时,可最后还是0ms。:)
Source Code
Problem: 2907 |
|
User: QuXiao |
Memory: 176K |
|
Time: 0MS |
Language: C++ |
|
Result: Accepted |
#include <iostream>
#include <climits>
using namespace std;
struct Point
{
int x, y;
};
int num, X, Y;
Point start, beeper[15];
int shortest;
int visited[15];
int Length (Point p1, Point p2)
{
return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}
void Input ()
{
int i;
cin>>X>>Y;
cin>>start.x>>start.y;
cin>>num;
for (i=0; i<num; i++)
cin>>beeper[i].x>>beeper[i].y;
}
void DFS (int cur, int len, int n)
{
if ( n == num )
{
int t = Length(beeper[cur], start);
if ( len + t < shortest )
shortest = len + t;
}
else if ( len < shortest )
{
int i;
for (i=0; i<num; i++)
{
if ( visited[i] == 0 )
{
visited[i] = 1;
DFS (i, len+Length(beeper[cur], beeper[i]), n+1);
visited[i] = 0;
}
}
}
}
void Solve ()
{
int i, t;
shortest = INT_MAX;
memset(visited, 0, sizeof(visited));
for (i=0; i<num; i++)
{
t = Length(beeper[i], start);
visited[i] = 1;
DFS (i, t, 1);
visited[i] = 0;
}
cout<<"The shortest path has length "<<shortest<<endl;
}
int main ()
{
int test;
cin>>test;
while ( test-- )
{
Input ();
Solve ();
}
return 0;
}