#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( 
00, t ) ); 

    
while!q.empty() )
    {
        
int u= q.front().u, total= q.front().total;
        bitset
<12> state= q.front().state; q.pop();

        
bool ok= true;
        
forint 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;
        }

        
forint 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 );
        
forint 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 阅读(129) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理