#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
int abs( int a, int b )
{
return a> b? a- b: b- a;
}
struct Point
{
int x, y;
Point(){}
Point( int a, int b ): x(a), y(b) {}
};
struct Node
{
int u, total;
bitset<12> state;
Node(){}
Node( int a, int b, bitset<12> c ): u(a), total(b), state(c) {}
};
int r, c,result,n;
vector<Point> map;
bool visite[25][25];
int graph[15][15];
void bfs()
{
queue<Node> q;
bitset<12> t; t.reset ();
q.push( Node( 0, 0, t ) );
while( !q.empty() )
{
int u= q.front().u, total= q.front().total;
bitset<12> state= q.front().state; q.pop();
bool ok= true;
for( int i= 0; i<= n; ++i )
if( state[i]== 0 ) ok= false;
if( ok )
{
if( total+ graph[u][0]< result ) result= total+ graph[u][0];
continue;
}
for( int i= 0; i<= n; ++i )
{
bitset<12> t= state;
if( t[i]== 0 && total+ graph[u][i]< result )
{
t[i]= 1;
q.push( Node( i, total+ graph[u][i], t ) );
}
}
}
}
int main()
{
int test;
scanf("%d",&test);
while( test-- )
{
map.clear();
scanf("%d%d",&r,&c);
int a,b;
scanf("%d%d",&a,&b); map.push_back( Point( a, b ) );
scanf("%d",&n );
for( int i= 0; i< n; ++i )
{
scanf("%d%d",&a,&b);
map.push_back( Point(a,b) );
}
for( size_t i= 0; i< map.size(); ++i )
for( size_t j= 0; j< map.size(); ++j )
graph[i][j]= abs( map[i].x- map[j].x )+ abs( map[i].y- map[j].y );
result= 1<<30;
bfs();
printf("The shortest path has length %d\n", result );
}
return 0;
}
posted on 2008-12-24 20:22
Darren 閱讀(131)
評(píng)論(0) 編輯 收藏 引用