完啦7AC + 3 MLE了已解决
原题链接：8048.马的遍历
2024-11-20 21:35:46
发布于：广东
25阅读
0回复
0点赞
#include <bits/stdc++.h>
using namespace std;
int x,y,n,m;
int dir[8][2] = {{-2,-1},{-2,1},{1,2},{-1,2},{2,1},{2,-1},{-1,-2},{1,-2}};
int mp[405][405];
bool vis[405][405];
struct node{
int x,y,s;
};
int main(){
memset(mp,-1,sizeof mp);
cin >> n >> m >> x >>y;
queue<node>q;
q.push({x,y,0});
while(!q.empty()){
auto f = q.front();
q.pop();
vis[f.x][f.y] = 1;
mp[f.x][f.y] = f.s;
for(int i=0;i<8;i++){
int nx = f.x + dir[i][0],ny = f.y + dir[i][1];
if(nx < 1 or nx > n or ny < 1 or ny > m)continue;
if(vis[nx][ny])continue;
q.push({nx,ny,f.s+1});
}
}for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
cout << mp[i][j] << " ";
cout << endl;
}
}
全部评论 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
有帮助，赞一个