【题解】洛谷马的遍历

马的遍历

方法：广度优先搜索

源代码如下

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

struct coord{
    //结构体定义x,y坐标
    int x , y;
};

queue <coord> Q;
int ans[500][500];  // -1代表未访问
int walk[8][2] = {{2 , 1} , {1 , 2} , {-1 , 2} , {-2 , 1} , {-2 , -1} , {-1 , -2} , {1 , -2} , {2 , -1}};

int main(){
    int n , m , sx , sy;
    memset(ans , -1 , sizeof(ans));
    cin >> n >> m >> sx >> sy;
    coord tmp = {sx , sy};
    Q.push(tmp);
    ans[sx][sy] = 0;
    while(!Q.empty()){
        coord u = Q.front();
        int ux = u.x , uy = u.y;
        Q.pop();
        for(int k = 0 ; k < 8 ; k ++){
            int x = ux + walk[k][0] , y = uy + walk[k][1];
            int d = ans[ux][uy];
            if(x < 1 || x > n || y < 1 || y > m || ans[x][y] != -1)    //判断是否超出范围或被访问
                continue;
            ans[x][y] = d + 1;
            coord tmp = {x , y};
            Q.push(tmp);    //符合要求，入栈
        }
    }
    for(int i = 1 ; i <= n ; i ++ , puts("")){
        for(int j = 1 ; j <= m ; j ++){
            printf("%-5d" , ans[i][j]);
        }
    }
    return 0;
}

注意：二维数组赋值一定要用memset

memset用法：memset(函数名 , 数值 , 列表长度(可以直接用sizeof（列表名));