求调

P1443 马的遍历

Beacon_wolf @ 2024-11-30 08:22:10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,sx,sy,ans[410][410];
bool vis[410][410];
int nx[8] = {-2,-1,1,2,2,1,-1,-2},ny[8] = {1,2,2,1,-1,-2,-2,-1};
struct Node{
    int x,y,dep;
};
queue<Node> q;
int read(){
    int x = 0,w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')   w = -w;
        ch = getchar();
    }
    while(ch >= '0'&& ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return w * x;
}
void print(int x){
    if(x < 0) putchar('-'),x = -x;
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int main(){
    cin >> n >> m >> sx >> sy;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            ans[i][j] = -1;
            vis[i][j] = false;
        }
    }
    q.push({sx,sy,0});
    while(!q.empty()){
        int kx = q.front().x,ky = q.front().y,d = q.front().dep;
        q.pop();
        ans[kx][ky] = d,vis[kx][ky] = true;
        for(int i = 0;i < 8;i++){
            int x = kx = nx[i],y = ky + ny[i];
            //cout << x << " " << y << " " << vis[x][y] << endl;
            if(x >= 1 && y >= 1 && x <= n && y <= m) if(!vis[x][y]) q.push({x,y,d + 1});
        }
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
} 

坐标移动自查过没有问题,但不知道为什么从第三次跳跃就变成“1 3”而不是设置的“2 3”了。


by piano_pei @ 2024-11-30 09:13:40

@Beacon_wolf

摘录几个错误 :

  1. x应该等于kx + nx[i], 但写成了x = kx = nx[i]
  2. 你在每次出队后标记,这可能导致一些数重复出入,建议现在bfs初始化时将vis[sx][sy]标记为1,往后在扩展节点的for循环中,如果拓展了一个新节点,直接标记,即标记vis[x][y] = 1
  3. 优化小建议。因为已经有ans数组,你没必要再queue里在写一个dep,完全可以直接读ans里的值,点(x,y)的dep就是ans[x][y],所以在扩展的时候可以写一个ans[x][y] = ans[kx][ky] + 1,这样转移得到点(kx,ky)的dep
  4. 这是我根据上述建议给你改的bfs部分的代码,实测AC:
    q.push({sx,sy});
    vis[sx][sy] = 1;
    ans[sx][sy] = 0;
    while(!q.empty()){
    int kx = q.front().x,ky = q.front().y;
    q.pop();
    for(int i = 0;i < 8;i++){
      int x = kx + nx[i],y = ky + ny[i];
      //cout << x << " " << y << " " << vis[x][y] << endl;
      if(x >= 1 && y >= 1 && x <= n && y <= m) 
      {
        if(!vis[x][y]) 
        {
            q.push({x,y});
            vis[x][y] = 1;
            ans[x][y] = ans[kx][ky] + 1;
        }
      }
    }
    }

最后,求关注qwq


by Beacon_wolf @ 2024-11-30 11:08:38

@piano_pei 已关,谢谢佬!


|