9073 关系网络 广搜 队列

解决思路

• 广度优先搜索 (BFS)：使用 BFS 从起点 x 开始搜索，找到到达终点 y 的最短路径。

• 队列：使用队列存储当前节点和步数。

• 访问标记：使用数组 vis 标记节点是否被访问过，防止重复访问。

  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int N = 1e3+10; // 定义常量N，表示最大节点数
  
  // 定义节点结构，包含当前节点编号和步数
  struct node {
      int x, step;
  };
  
  int g[N][N]; // 邻接矩阵，表示节点之间的关系
  int vis[N]; // 访问标记数组，防止重复访问
  int n, s, e; // n表示节点数，s表示起点，e表示终点
  int ans; // 存储最终答案
  
  // 广度优先搜索函数
  void bfs() {
      queue<node> q; // 定义队列用于BFS
      q.push({s, 0}); // 将起点加入队列，初始步数为0
      vis[s] = 1; // 标记起点已访问
  
      while(q.size()) { // 当队列不为空时
          int x = q.front().x, step = q.front().step; // 获取队首节点和步数
          q.pop(); // 弹出队首节点
  
          for(int i = 1; i <= n; i++) { // 遍历所有节点
              if(g[x][i] && !vis[i]) { // 如果节点i与当前节点x相连且未被访问
                  q.push({i, step + 1}); // 将节点i加入队列，步数加1
                  vis[i] = 1; // 标记节点i已访问
  
                  if(i == e) { // 如果节点i是终点
                      cout << step; // 输出步数,比较特殊，不需要step+1
                      return; // 结束搜索
                  }
              }
          }
      }
  }
  
  int main() {
      cin >> n >> s >> e; // 读取节点数、起点和终点
      for(int i = 1; i <= n; i++) // 读取邻接矩阵
          for(int j = 1; j <= n; j++)
              cin >> g[i][j];
      bfs(); // 调用BFS函数
      return 0; // 返回0，表示程序正常结束
  }