MLE+WA+AC

原题链接：8048.马的遍历
userId_undefined

四斋臻瞎投

倔强青铜

2024-08-06 09:50:59

发布于：浙江

45阅读
0回复
0点赞

成分复杂，有没有大佬帮忙改改

#include<iostream>
#include<queue>
using namespace std;
struct node{
    int x,y;
    int step;
};
int m,n,x,y,dir[8][2]={{1,2},{-1,2},{1,-2},{-1,-2},{2,1},{-2,1},{2,-1},{-2,-1}},vis[410][410];
int main(){
    int m,n,x,y;
    cin>>m>>n>>x>>y;
    queue<node> q;
	for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            q.push({x,y,0});
            while(!q.empty()){
       			node t=q.front();
      			q.pop();
                if(t.x==i&&t.y==j){
                    cout<<t.step<<" ";
                    break;
                }
                for(int i=0;i<=7;i++){
                    int nx=t.x+dir[i][0],ny=t.y+dir[i][1];
                    if(nx<=m&&nx>=1&&ny<=n&&ny>=1&&vis[nx][ny]!=1){
                        q.push({nx,ny,t.step++});
                        vis[nx][ny]=1;
                    }
                }
    		}
        }
        cout<<"\n";
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 2

  • userId_undefined

    ༺ཌༀ傲世万物ༀད༻

    倔强青铜

    你的代码存在一些逻辑错误和性能问题。让我们逐步分析并改进它。问题分析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天前 来自 浙江

    1
  • userId_undefined

    我就是我

    倔强青铜
    #include <iostream>
#include <queue>
using namespace std;

int dist[401][401];
const int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
const int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs(int x, int y, int n, int m) {
    // 初始化
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dist[i][j] = -1;
        }
    }
    dist[x][y] = 0;
    
    queue<pair<int, int>> q;
    q.push({x, y});
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        for (int k = 0; k < 8; k++) {
            int nx = cx + dx[k], ny = cy + dy[k];
            
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[cx][cy] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    bfs(x, y, n, m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

    2024-08-11 来自 广东

    0

热门讨论