用循环队列进行广度搜索

用循环队列求解一个问题
F 神正在爬楼梯，他从第 0 级台阶出发，想要爬到第 P 级台阶。他一次可以爬的台阶数目
是固定的，为 a1, a2, ，, aN 这 N 个数中的一个。
由于年久失修，一共有 M 级台阶损坏了，分别为 b1, b2, ， , bM 级台阶，如果走上这些台
阶，F 神就会坠落。
请问是否存在方案，使得 F 神能够爬到第 P 级台阶？
Input
输入共五行。
输入的第一行为一个正整数 N。
输入的第二行为 N 个正整数，第 i 个为 ai。
输入的第三行为一个正整数 M。
输入的第四行为 M 个正整数，第 i 个为 bi。
输入的第五行为 P。
Output
输出一行一个字符串，若可以爬到，输出 Yes，否则输出 No。

#include
#define MAXN 1000
int N;
int n[15];
int M;
int m[MAXN]={0};
int p;
int queue[MAXN];
int head=0,tail=0;
void push(int x){
    if((tail+1)%MAXN==head){
        return ;
    }else{
         
        tail=(tail+1)%MAXN;
        queue[tail]=x;
    }
}
int  pop(void){
    if(head==tail){
        return 0;
    } else{
        
        head=(head+1)%MAXN; 
        return queue[head];
    }
}
int main(){

    scanf("%d",&N);

    int i;
    for(i=1;i<=N;i++){
        scanf("%d",&n[i]);
    }

    scanf("%d",&M);

    int t;
    for(i=1;i<=M;i++){
        scanf("%d",&t);
        m[t]=1;
    }
    scanf("%d",&p);
    queue[0]=0;
    tail=1;

    while(head!=tail && queue[head]int t=pop();
        printf("t=%d head=%d tail =%d\n",t,head,tail);
        for(i=1;i<=N;i++){
            if(m[t+n[i]]==0){
                push(t+n[i]);
                m[t+n[i]]=1;
            }
        } 

    }
    if(queue[head]==p){
        printf("Yes");
    }else{
        printf("No");
    }


    return 0;
}

我在输入1 1 0 1050后
输出结果：

t=993 head=994 tail =995
t=994 head=995 tail =996
t=995 head=996 tail =997
t=996 head=997 tail =998
t=997 head=998 tail =999
t=998 head=999 tail =0
t=999 head=0 tail =0
No

跑到最后一行tail＝0时并未将999压入循环队列
程序提前结束，想知道是哪里不对

基于Monster 组和GPT的调写：

队列的大小被定义为#define MAXN 1000，也就是说，队列的最大长度为1000。但是在你的代码中，并没有判断队列的长度是否超过了最大值，也就是说，你的队列长度是不受限制的，因此，在输入1 1 0 1050后，当队列中元素的数量超过了1000时，程序会崩溃
push函数中加一个：

if((tail+1)%MAXN == head){
    // 队列已满，无法添加新元素
    return;
}

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7634730
• 除此之外, 这篇博客: C语言实现八大排序算法详解及其性能之间的中的 这里需要对堆有一定的了解，堆就是一个比较特殊的完全二叉树，在最大堆里，每个节点的值都大于其左右两个孩子节点的值。这就是最大堆。反之就是最小堆。拿最大堆举例子，每次堆顶的元素值，不就是当前数列的最大吗？这不就成选择排序里的简单排序了吗？找完之后，将他和完全二叉树里最后一个结点的值进行交换，然后做一个自顶向下的自我调整，将他再次调整成一个完全二叉堆。第二次取最大的树，这时我们需要将上一次找到的结点屏蔽掉，不然会陷入一个死循环。无数次找完之后，再按层序的思想将二叉树里的数据遍历到一个数组当中，这时的数组为一个有序的数组。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  算法思想

• 以下回答来自chatgpt:

  经过分析，该问题可能存在以下几个方面的问题：

  1. 程序的输入参数是否正确，是否有输入错误或者输入格式不规范的情况？
  2. 程序的算法逻辑是否正确，是否有逻辑错误导致程序未能正常执行？
  3. 程序的代码是否规范，是否存在语法错误、格式错误等问题导致程序无法执行？
  4. 程序的调试是否充分，是否对程序进行充分的测试和调试，是否对程序可能出现的错误做好充分的防范工作？

  对于该问题，我们可以先检查输入参数是否正确，如果输入有问题，可以对输入进行格式化和纠错处理；如果输入正确，可以对程序的算法逻辑进行调试和检查，对程序的代码进行修正和规范化，同时加强对程序的测试和调试，以确保程序能够正常运行并得到正确的结果。

  针对该问题，下面给出一个可能的解决方案：

  1. 检查输入参数：针对给出的测试用例，我们发现输入参数为1、1、0和1050，可以先检查是否有输入错误或者输入格式不规范的情况。具体做法可以使用Python中的input()函数获取输入参数，然后分别进行类型检查和值检查，如果发现输入参数有误，可以给出相应的提示，并要求用户重新输入。如果输入正确，则可以继续进行程序的执行。代码示例如下：

  n = input("请输入总台阶数n：")
  if not n.isdigit() or int(n) <= 0:
      print("输入有误，请输入一个正整数！")
      n = input("请输入总台阶数n：")
  a = input("请输入可爬台阶数（以逗号隔开）：")
  a_list = a.split(",")
  for i in a_list:
      if not i.isdigit() or int(i) <= 0:
          print("输入有误，请输入一个正整数！")
          a = input("请输入可爬台阶数（以逗号隔开）：")
          a_list = a.split(",")
  m = input("请输入已损坏的台阶数m：")
  if not m.isdigit() or int(m) <= 0:
      print("输入有误，请输入一个正整数！")
      m = input("请输入已损坏的台阶数m：")
  b = input("请输入已损坏的台阶列表（以逗号隔开）：")
  b_list = b.split(",")
  for i in b_list:
      if not i.isdigit() or int(i) < 0 or int(i) >= int(n):
          print("输入有误，请输入一个有效的台阶位置！")
          b = input("请输入已损坏的台阶列表（以逗号隔开）：")
          b_list = b.split(",")
  p = int(n)    # 目的地为第p级台阶
  

  1. 检查程序的算法逻辑：针对循环队列广度搜索算法，我们需要检查算法是否正确，是否漏掉了某些情况导致程序无法正常执行。具体做法可以在代码中逐行进行调试，加入调试语句以检查每一步的执行情况，并配合使用断点调试工具以及输出日志等方式进行调试。如果发现程序有问题，可以对算法逻辑进行修正和改进，直到程序能够正常运行并得到正确的结果。代码示例如下：

  q = [0] * (int(n) + 1)   # 队列
  visited = [False] * (int(n) + 1)   # 标记数组
  head = 0    # 队首
  tail = 0    # 队尾
  q[tail] = 0    # 入队
  tail += 1
  visited[0] = True    # 标记为已访问
  while head < tail:
      cur = q[head]    # 取出队首
      head += 1
      for i in range(len(a_list)):
          next_step = cur + int(a_list[i])    # 计算下一步的位置
          if next_step == p:    # 到达目的地
              print("F神可以到达第{}级台阶！".format(p))
              break
          if next_step > p:    # 超出目的地
              continue
          if visited[next_step]:    # 已经访问过
              continue
          if str(next_step) in b_list:    # 损坏的台阶
              continue
          q[tail] = next_step    # 入队
          tail += 1
          visited[next_step] = True    # 标记为已访问
      if cur == p:   # 找到目的地后退出循环
          break
  if cur != p:
      print("F神无法到达第{}级台阶！".format(p))
  

  1. 检查程序的代码规范：为了确保程序能够正常执行，我们需要检查程序的代码是否规范，是否存在语法错误、格式错误等问题。具体做法可以使用代码编辑器自带的语法检查和代码格式化工具进行检查和优化，同时也可以借助第三方的代码检查工具进行检查和优化。如果发现代码存在问题，可以对代码进行修正和规范化，以确保程序能够正常执行。代码示例如下：

  # 主程序
  n = input("请输入总台阶数n：")
  if not n.isdigit() or int(n) <= 0:
      print("输入有误，请输入一个正整数！")
      n = input("请输入总台阶数n：")
  a = input("请输入可爬台阶数（以逗号隔开）：")
  a_list = a.split(",")
  for i in a_list:
      if not i.isdigit() or int(i) <= 0:
          print("输入有误，请输入一个正整数！")
          a = input("请输入可爬台阶数（以逗号隔开）：")
          a_list = a.split(",")
  m = input("请输入已损坏的台阶数m：")
  if not m.isdigit() or int(m) <= 0:
      print("输入有误，请输入一个正整数！")
      m = input("请输入已损坏的台阶数m：")
  b = input("请输入已损坏的台阶列表（以逗号隔开）：")
  b_list = b.split(",")
  for i in b_list:
      if not i.isdigit() or int(i) < 0 or int(i) >= int(n):
          print("输入有误，请输入一个有效的台阶位置！")
          b = input("请输入已损坏的台阶列表（以逗号隔开）：")
          b_list = b.split(",")
  p = int(n)  # 目的地为第p级台阶
  q = [0] * (int(n) + 1)  # 队列
  visited = [False] * (int(n) + 1)  # 标记数组
  head = 0  # 队首
  tail = 0  # 队尾
  q[tail] = 0  # 入队
  tail += 1
  visited[0] = True  # 标记为已访问
  while head < tail:
      cur = q[head]  # 取出队首
      head += 1
      for i in range(len(a_list)):
          next_step = cur + int(a_list[i])  # 计算下一步的位置
          if next_step == p:  # 到达目的地
              print("F神可以到达第{}级台阶！".format(p))
              break
          if next_step > p:  # 超出目的地
              continue
          if visited[next_step]:  # 已经访问过
              continue
          if str(next_step) in b_list:  # 损坏的台阶
              continue
          q[tail] = next_step    # 入队
          tail += 1
          visited[next_step] = True  # 标记为已访问
      if cur == p:    # 找到目的地后退出循环
          break
  if cur != p:
      print("F神无法到达第{}级台阶！".format(p))
  

  1. 加强程序的测试和调试：为了保证程序的稳定可靠性，我们需要加强对程序的测试和调试，尤其是对于可能出现的错误情况需要做好充分的防范工作。具体做法可以利用各种测试工具、调试工具以及输出日志等手段，对程序的各个部分进行全面的测试和调试。如果发现程序有问题，可以针对问题进行逐步排查和定位，最终得到正确的解决方案。代码示例如下：

  # 主程序
  # （同上，略）
  
  # 模拟input()输入，进行测试
  import io
  input_data = '10\n2,3,5\n2\n3,5\n7\n'
  input_data = io.StringIO(input_data).readline
  print("测试用例1：总台阶数为10，可爬台阶数为2、3和5，共有2个已损坏的台阶，测试目的地为第7级台阶。")
  n = input("请输入总台阶数n：", strip)
  a = input("请输入可爬台阶数（以逗号隔开）：", strip)
  m = input("请输入已损坏的台阶数m：", strip)
  b = input("请输入已损坏的台阶列表（以逗号隔开）：", strip)
  p = int(n)  # 目的地为第p级台阶
  q = [0] * (int(n) + 1)  # 队列
  visited = [False] * (int(n) + 1)  # 标记数组
  head = 0  # 队首
  tail = 0  # 队尾
  q[tail] = 0  # 入队
  tail += 1
  visited[0] = True  # 标记为已访问
  while head < tail:
      cur = q[head]  # 取出队首
      head += 1
      for i in range(len(a_list)):
          next_step = cur + int(a_list[i])  # 计算下一步的位置
          if next_step == p:  # 到达目的地
              print("F神可以到达第{}级台阶！".format(p))
              break
          if next_step > p:  # 超出目的地
              continue
          if visited[next_step]:  # 已经访问过
              continue
          if str(next_step) in b_list:  # 损坏的台阶
              continue
          q[tail] = next_step  # 入队
          tail += 1
          visited[next_step] = True  # 标记为已访问
      if cur == p:  # 找到目的地后退出循环
          break
  if cur != p:
      print("F神无法到达第{}级台阶！".format(p))
  
  # 输出日志，进行测试
  import logging
  logging.basicConfig(filename='queue_alg.log', level=logging.INFO)
  logging.info('测试用例1：总台阶数为10，可爬台阶数为2、3和5，共有2个已损坏的台阶，测试目的地为第7级台阶。')
  n = 10
  a_list = [2, 3, 5]
  m = 2
  b_list = [3, 5]
  p = n
  q = [0] * (int(n) + 1)
  visited = [False] * (int(n) + 1)
  head = 0
  tail = 0
  q[tail] = 0
  tail += 1
  visited[0] = True
  while head < tail:
      cur = q[head]
      head += 1
      for i in range(len(a_list)):
          next_step = cur + int(a_list[i])
          if next_step == p:
              logging.info("F神可以到达第{}级台阶！".format(p))
              break
          if next_step > p:
              continue
          if visited[next_step]:
              continue
          if str(next_step) in b_list:
              continue
          q[tail] = next_step
          tail += 1
          visited[next_step] = True
      if cur == p:
          break
  if cur != p:
      logging.info("F神无法到达第{}级台阶！".format(p))
  

  参考资料：

  • Python3官方文档：https://docs.python.org/3/library/index.html
  • 《Python数据结构与算法分析》
  • 《算法（第四版）》

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^