QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
    地图上有一些beeper,让你从起点搜集所有beeper,再回到起点。但你只可以水平或者竖直的走,不能走对角线。让你找出这样走的最短路径长度。
    因为地图最大只有20×20,而beeper最多也只有10个,所以可以考虑用深搜,找到所有可能路径,在其中加一些简单的减枝就可以了。起初以为会超时,可最后还是0ms。:)

Source Code

Problem: 2907
User: QuXiao
Memory: 176K
Time: 0MS
Language: C++
Result: Accepted
  • Source Code
  • #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;
    }



posted on 2007-12-07 19:31 quxiao 阅读(365) 评论(1)  编辑 收藏 引用 所属分类: ACM

评论

# re: PKU2907 Collecting Beepers 2008-01-26 04:35 richardxx
嗯,努力,一定会成功的,你的代码还写得不错,:>  回复  更多评论
  


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