求助各位大佬!为什么我家马bfs只会判断一个格子的步数......
查看原帖
求助各位大佬!为什么我家马bfs只会判断一个格子的步数......
640657
White_eyes楼主2022/4/5 14:29
#include<iostream>
#include<queue>
using namespace std;
struct point{
    int x, y, step;
};
queue<point> r;
int n, m, flag;
const int Er = -1;
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}, dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};
bool v[101][101];//是否已访问
int main()
{
    point start;
    start.step = 0;
    scanf("%d%d%d%d", &n, &m, &start.x, &start.y);
    v[start.x][start.y] = true;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            r.push(start);
            flag = 0;
            while(!r.empty()){
                int x = r.front().x, y = r.front().y;
                if(x == i && y == j){
                    printf("%-5d", r.front().step);
                    flag = 1;
                    break;
                }
                for(int t = 0; t < 8; t++){
                    int tx = x + dx[t], ty = y + dy[t];
                    if(tx < 1 || tx > n || ty < 1 || tx > m || v[tx][ty]) continue;//出界或走过就不走
                    point temp;
                    temp.x = tx;
                    temp.y = ty;
                    temp.step = r.front().step + 1;
                    r.push(temp);
                    v[tx][ty] = true;
                }
                r.pop();
            }
            if(!flag) printf("%-5d", Er);
        }
        printf("\n");
    }
    return 0;
}

输入3 3 1 1

输出

0 3 -1

-1 -1 -1

-1 -1 -1

2022/4/5 14:29
加载中...