pta 编程题16 Saving James Bond - Easy Version

我就是我 2021-10-26 11:42 226阅读 0赞

其它pta数据结构编程题请参见：**[pta][]**

**[题目][Link 1]**

主要用到了深度优先搜索。

1 #include <iostream>
     2 using namespace std;
     3 
     4 struct Vertex
     5 {
     6     int x;
     7     int y;
     8     bool marked;
     9 }G[100];
    10 
    11 int N; //总鳄鱼数
    12 int D; //可以跳的距离
    13 bool dfs(Vertex& v);
    14 bool firstJump(Vertex v);
    15 bool jump(Vertex v1, Vertex v2);
    16 bool success(Vertex v); //可以跳到岸上
    17 
    18 int main()
    19 {
    20     int i;
    21     cin >> N >> D;
    22     for (i = 0; i < N; i++)
    23         cin >> G[i].x >> G[i].y;
    24 
    25     bool canEscape = false;
    26     for (i = 0; i < N; i++)
    27     {
    28         if (!G[i].marked && firstJump(G[i]))
    29             canEscape = dfs(G[i]);
    30         if (canEscape) break;
    31     }
    32     if (canEscape) cout << "Yes";
    33     else cout << "No";
    34     return 0;
    35 }
    36 
    37 bool firstJump(Vertex v)
    38 {
    39     return v.x * v.x + v.y * v.y <= (15 + D) * (15 + D);
    40 }
    41 
    42 bool dfs(Vertex& v)
    43 {
    44     bool canEscape = false;
    45     v.marked = true;
    46     if (success(v)) return true;
    47     for (int i = 0; i < N; i++)
    48     {
    49         if (!G[i].marked && jump(v, G[i]))
    50             canEscape = dfs(G[i]);
    51         if (canEscape) break;
    52     }
    53     return canEscape;
    54 }
    55 
    56 bool success(Vertex v)
    57 {
    58     if (v.x <= D - 50 || v.x >= 50 - D || v.y <= D - 50 || v.y >= 50 - D)
    59         return true;
    60     return false;
    61 }
    62 
    63 bool jump(Vertex v1, Vertex v2)
    64 {
    65     return (v1.x - v2.x) * (v1.x - v2.x) + (v1.y - v2.y) * (v1.y - v2.y) <= D*D;
    66 }

转载于:https://www.cnblogs.com/lxc1910/p/8969105.html

[pta]: http://www.cnblogs.com/lxc1910/p/8811251.html
[Link 1]: https://pintia.cn/problem-sets/951072707007700992/problems/982816780864188416