完啦7AC + 3 MLE了已解决

全部评论 2

• 

  ༺ཌༀ傲世万物ༀད༻

  

  你的代码存在一些逻辑错误和性能问题。让我们逐步分析并改进它。问题分析1. 初始化问题：你在每次内层循环中都重新将起始点 (x, y) 入队，这会导致重复计算和效率低下。2. 访问标记：你在每次内层循环中都重新初始化 vis 数组，这会导致重复计算。3. 步数更新：你在 t.step++ 时直接修改了 t.step，这会导致步数错误。改进后的代码：

  
  
  
  #include <iostream>
  #include <queue>
  using namespace std;
  
  struct node {
      int x, y;
      int step;
  };
  
  int n, m, x, y;
  int dir[8][2] = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};
  int vis[410][410];
  int dist[410][410];
  
  void bfs() {
      queue<node> q;
      q.push({x, y, 0});
      vis[x][y] = 1;
  
      while (!q.empty()) {
          node t = q.front();
          q.pop();
  
          for (int i = 0; i < 8; i++) {
              int nx = t.x + dir[i][0];
              int ny = t.y + dir[i][1];
  
              if (nx >= 1 &&nx <= n &&ny >= 1 &&ny <= m &&!vis[nx][ny]) {
                  q.push({nx, ny, t.step + 1});
                  vis[nx][ny] = 1;
                  dist[nx][ny] = t.step + 1;
              }
          }
      }
  }
  
  int main() {
      cin >> n >> m >> x >> y;
  
      // 初始化距离数组为 -1
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= m; j++) {
              dist[i][j] = -1;
          }
      }
  
      // 起始点的距离为 0
      dist[x][y] = 0;
  
      bfs();
  
      // 输出结果
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= m; j++) {
              cout << dist[i][j] << " ";
          }
          cout << "\n";
      }
  
      return 0;
  }
  

  代码解释1. 结构体定义：定义了一个 node 结构体，包含坐标 (x, y) 和步数 step。2. 方向数组：定义了八个方向的移动数组 dir。3. 初始化： •vis 数组用于标记访问过的点。•dist 数组用于存储从起始点到每个点的最小步数，初始值为 -1。4. BFS 函数： •将起始点 (x, y) 入队，并标记为已访问，步数为 0。•使用队列进行广度优先搜索，每次出队一个节点，尝试向八个方向移动。•如果新位置在棋盘范围内且未被访问过，则将其入队，标记为已访问，并更新步数。5. 主函数： •读取输入。•初始化 dist 数组。•调用 bfs 函数。•输出结果，每个点的最小步数。这样改进后，代码的逻辑更清晰，性能也得到了提升。希望这能解决你的问题！如果有任何疑问或需要进一步的解释，请随时告诉我。

  5天前 来自 浙江

  0
• 

  Macw07

  

  

  看到你这边已经通过这道题目了，如果没有问题的话可以在帖子标题中注明【已解决】的字眼。

  2024-09-03 来自 加拿大

  0