马的遍历

题目 马的遍历

思路分析

如果是单纯的相邻拓展 这道题就只要简单的把d数组输出一下就行了

但是 题目隐含了一个条件——马走日

所以对于每一个点 不是拓展它相邻的四个方向了

而是拓展它走日的八个方向

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

const int N=410;

int d[N][N];

int n,m,x,y;

int dx[8]={-2,-1,1,2,2,1,-1,-2};

int dy[8]={1,2,2,1,-1,-2,-2,-1};

bool isVaild(int x,int y){

	return x>=1 && x<=n && y>=1 && y<=m && d[x][y]==-1;

}

void bfs(int x,int y){

	queue<PII> q;

	memset(d,-1,sizeof d);

	q.push({x,y});

	d[x][y]=0;

	while(!q.empty()){

		auto cur=q.front();q.pop();

		int ux=cur.first,uy=cur.second;

		for(int i=0;i<8;i++){

			int nx=ux+dx[i],ny=uy+dy[i];

			if(isVaild(nx,ny)){

				d[nx][ny]=d[ux][uy]+1;

				q.push({nx,ny});

			}

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m>>x>>y;

	bfs(x,y);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++){

			printf("%-5d",d[i][j]);//左对齐右补到5位

		}

		printf("\n");

	}

	return 0;

 }

同类题型

视频讲解

⬅️ 迷宫问题（最短路） 🏠 00-刷题理模型 ➡️ DFS BFS相关模型