摘要
Title: 1855. 愤怒的奶牛
Tag: BFS、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1855. 愤怒的奶牛

• 题意

  奶牛贝茜设计了一款她认为必火的游戏：愤怒的奶牛。
  游戏设定（她坚信这是她的原创）是玩家用一个弹弓将一头奶牛射向一个数轴，数轴的不同位置上分布着一些干草捆。
  奶牛以足够的力量砸向某个干草捆，并使得该干草捆发生爆炸，爆炸可能会不断引起连锁反应，导致更多的干草捆发生爆炸。
  目标是用一头奶牛引起的连锁反应引爆尽可能多的干草捆。
  共有 N 个干草捆位于数轴中的不同整数位置，其坐标依次为 x1,x2,…,xN。
  如果将奶牛射向位于位置 x 的干草捆，则该干草捆发生爆炸，爆炸半径为 1，爆炸将吞噬 1 单位距离内的所有干草捆。
  然后这些干草捆（全部同时）发生爆炸，每个干草捆的爆炸半径为 2。
  二次爆炸中吞噬的所有尚未爆炸的干草捆也（全部同时）发生爆炸，爆炸半径为 3。
  也就是说，在 t 时刻爆炸的干草捆的爆炸半径为 t，其爆炸波及的干草捆在 t+1 时刻也会爆炸，爆炸半径为 t+1，以此类推。
  请确定，通过合理选择奶牛射向的干草捆，能够引爆的干草捆最大数量。

• 思路

  $O(n^3)$做法：枚举每个点进行BFS

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-01-25 22:18:56
  FilePath: \ACM\Acwing\1855.py
  LastEditTime: 2022-01-25 22:44:48
  '''
  from collections import deque
  
  N = 105
  A = []
  
  
  def bfs(k):
      q = deque()
      vis = [0] * N
  
      cnt = 1
      q.appendleft([k, cnt])
      # 下标，爆炸范围
      vis[k] = 1
      res = 0
      while len(q):
          tmp = q.pop()
          k = tmp[0]
          cnt = tmp[1]
          res += 1
          for i in range(k):
              if A[i] >= A[k] - cnt and vis[i] == 0:
                  q.appendleft([i, cnt + 1])
                  vis[i] = 1
          for i in range(k + 1, n):
              if A[i] <= A[k] + cnt and vis[i] == 0:
                  q.appendleft([i, cnt + 1])
                  vis[i] = 1
      return res
  
  
  if __name__ == "__main__":
      n = int(input())
      for i in range(n):
          A.append(int(input()))
      A.sort()
  
      res = 0
      for i in range(n):
          res = max(res, bfs(i))
      print(res)