bfs洛谷p1443马的遍历

Question

洛谷p1443 马的遍历,我采用的是bfs，但是不知道哪里出错了过不了，想了很久，还是没搞明白，希望大家可以帮我看看

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N=410;
struct pos{
    int x;
    int y;
    int steps;
};
int n,m,Startx,Starty;
int vis[N][N];
int bx[8]={-1,-2,-2,-1,1,2,2,1};
int by[8]={-2,-1,1,2,-2,-1,1,2}; 
int check(int x,int y){
    if(x<1||x>n||y<1||y>m)
      return 0;
    return 1;
}
void bfs(int endx,int endy){
    pos cur,next;
    queue<pos>que;
    cur.x=Startx;
    cur.y =Starty;
    cur.steps =0;
    que.push(cur);
    vis[cur.x][cur.y ]=1;
    while(!que.empty()){
        cur=que.front();
        que.pop();
        if(cur.x==endx&&cur.y ==endy){
            printf("%d ",cur.steps );
            return ;
        }
        //接下来要循环八个方向
        //使用方向数组
        for(int i=0;i<8;i++){
            next.x=cur.x+bx[i];
            next.y=cur.y+by[i];
            next.steps =cur.steps +1;
            if(check(next.x,next.y)==1){
                if(vis[next.x][next.y ]==0)
                  vis[next.x ][next.y ]=1;
                  que.push(next);
            }
        } 
    }
    printf("-1\n");
    return ;
    
}

int main(){
    cin>>n>>m>>Startx>>Starty;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
          bfs(i,j);
        printf("\n");
    }
    return 0;
}

Answer 1

最幸运的小孩(ง •̀_•́)ง 晚上好🌙🌙🌙
本答案参考ChatGPT-3.5

在你的代码中，有一个小错误导致无法通过测试。在检查下一个位置时，你忘记了添加一个大括号来包裹需要执行的代码。这导致了vis数组的更新出现错误。在你的代码中，虽然通过了编译，但是实际上vis数组的更新只会在满足条件check(next.x, next.y) == 1时执行，而不会受到vis[next.x][next.y] == 0这个条件的限制。正确的代码应该如下所示：

#include <iostream>
#include <queue>
using namespace std;
const int N = 410;
struct pos {
    int x;
    int y;
    int steps;
};
int n, m, Startx, Starty;
int vis[N][N];
int bx[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int by[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };
int check(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m)
      return 0;
    return 1;
}
void bfs(int endx, int endy) {
    pos cur, next;
    queue<pos> que;
    cur.x = Startx;
    cur.y = Starty;
    cur.steps = 0;
    que.push(cur);
    vis[cur.x][cur.y] = 1;
    while (!que.empty()) {
        cur = que.front();
        que.pop();
        if (cur.x == endx && cur.y == endy) {
            printf("%d ", cur.steps);
            return;
        }
        for (int i = 0; i < 8; i++) {
            next.x = cur.x + bx[i];
            next.y = cur.y + by[i];
            next.steps = cur.steps + 1;
            if (check(next.x, next.y) == 1) {
                if (vis[next.x][next.y] == 0) {
                    vis[next.x][next.y] = 1;
                    que.push(next);
                }
            }
        }
    }
    printf("-1\n");
    return;
}

int main() {
    cin >> n >> m >> Startx >> Starty;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            bfs(i, j);
            memset(vis, 0, sizeof(vis)); // 重置vis数组
        }
        printf("\n");
    }
    return 0;
}

我对你的代码做了两处修改：

1. 在添加next节点到队列que之前，我添加了大括号来包住vis数组的更新语句，以确保vis数组只有在满足条件时才会更新。

2. 在每次开始新一轮bfs搜索之前，我添加了memset(vis, 0, sizeof(vis))语句来重置vis数组。因为每次搜索都是从Startx和Starty开始的，所以在开始新一轮搜索之前，需要重置vis数组，这样每个点都可以被重新访问。