浙大数据结构：06-图2 Saving James Bond - Easy Version

这道题是稍复杂版的dfs或bfs，此处我采用bfs实现

机翻：

1、条件准备

n为鳄鱼数量，jump为跳一次最大距离。

eyu数组对存每条鳄鱼的坐标位置，visit数组判断该鳄鱼是否走过，isalive判断到达该鳄鱼时能否逃离。

#include <iostream>
using namespace std;

int n, jump;
pair<int, int> eyu[10010];
bool visit[10005];
bool isalive[10005];

输入鳄鱼数量，跳跃最大距离。然后循环输入每条鳄鱼位置。

这里我加上偏置，使得坐标都为正数，存入进来。

如果坐标到岸边距离小于跳跃距离，那么该鳄鱼标记为1.

然后我们专门新开一条鳄鱼作为起始位置，也就是岛中心。

然后bfs一下，如果能逃出则输出Yes，不能则输出No。

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> jump;
  for (int i = 0; i < n; i++)
  {
    int a, b;
    cin >> a >> b;
    a += 50, b += 50;
    eyu[i].first = a, eyu[i].second = b;
    if (a <= jump || 100 - a <= jump || b <= jump || 100 - b <= jump)
      isalive[i] = 1;
  }
  eyu[10005].first = 50, eyu[10005].second = 50;

  if (bfs())
  {
    cout << "Yes";
    return 0;
  };
  cout << "No";
  return 0;
}

2、isjump函数

这个函数是判断从第a头鳄鱼到第b头鳄鱼之间距离是否小于dis

其实就是算两点之间距离再比较即可。

abs函数是取绝对值

bool isjump(int a, int b, int dis)
{
  int x = abs(eyu[a].first - eyu[b].first);
  int y = abs(eyu[a].second - eyu[b].second);
  if (x * x + y * y <= dis * dis)return 1;
  return 0;
}

3、bfs函数

还是用数组模拟队列，先单独处理一下起始位置能跳到的鳄鱼，都放进队列里，注意加上岛中间半径15,访问过visit置1

然后取队头，直到队列为空，然后扫描鳄鱼，看该鳄鱼能否跳到其它鳄鱼，能就放入队列。

如果跳到了鳄鱼是可逃离鳄鱼则返回1

int bfs()
{
  int q[20005], tt = -1, hh = 0;
  for (int i = 0; i < n; i++)
  {
    if (!visit[i] && isjump(10005, i, jump + 15))
    {
      q[++tt] = i;
      visit[i] = 1;
      if (isalive[i])  return 1;
    }
  }

  while (hh <= tt)
  {
    int cur = q[hh++];
    for (int i = 0; i < n; i++)
    {
      if (!visit[i] && isjump(cur, i, jump))
      {
        visit[i] = 1;
        q[++tt] = i;
        if (isalive[i])  return 1;
      }
    }
  }
  return 0;
}

4、总结

这道题理解题意稍微难一点，代码并不难。

完整代码如下：

#include <iostream>
using namespace std;

int n, jump;
pair<int, int> eyu[10010];
bool visit[10005];
bool isalive[10005];

bool isjump(int a, int b, int dis)
{
  int x = abs(eyu[a].first - eyu[b].first);
  int y = abs(eyu[a].second - eyu[b].second);
  if (x * x + y * y <= dis * dis)return 1;
  return 0;
}

int bfs()
{
  int q[20005], tt = -1, hh = 0;
  for (int i = 0; i < n; i++)
  {
    if (!visit[i] && isjump(10005, i, jump + 15))
    {
      q[++tt] = i;
      visit[i] = 1;
      if (isalive[i])  return 1;
    }
  }

  while (hh <= tt)
  {
    int cur = q[hh++];
    for (int i = 0; i < n; i++)
    {
      if (!visit[i] && isjump(cur, i, jump))
      {
        visit[i] = 1;
        q[++tt] = i;
        if (isalive[i])  return 1;
      }
    }
  }
  return 0;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> jump;
  for (int i = 0; i < n; i++)
  {
    int a, b;
    cin >> a >> b;
    a += 50, b += 50;
    eyu[i].first = a, eyu[i].second = b;
    if (a <= jump || 100 - a <= jump || b <= jump || 100 - b <= jump)
      isalive[i] = 1;
  }
  eyu[10005].first = 50, eyu[10005].second = 50;

  if (bfs())
  {
    cout << "Yes";
    return 0;
  };
  cout << "No";
  return 0;
}