题目
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1443
- 参考题解：https://www.luogu.com.cn/problem/solution/P1443
- 标签：
图、广搜、BFS
题解
- 小码匠思路
- 是比较标准的bfs题了，理论上dfs应该也行（不过你要承受TLE就是了），这里有个相当核心的常识啊，就是马是走日字的，一共有八个方向，不嫌麻烦就挨个if就行，推荐数组 循环的方式
- 官方题解
- 题解大家可移步看这里，很多童鞋写了各种解法
- https://www.luogu.com.cn/problem/solution/P1443
代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int a[403][403];
int n, m;
int b[403][403];
const int dx[8]={-1,-2,-2,-1,1,2,2,1};
const int dy[8]={2,1,-1,-2,2,1,-1,-2};
bool is (int x, int y) {
return (x >= 0 && x < n && y >= 0 && y < m) && !b[x][y];
}
struct edge {
int x, y;
};
queue<edge> v;
void bfs(int x, int y ) {
v.push({x, y});
while (!v.empty()) {
edge k = v.front();
v.pop();
for (int i = 0; i < 8; i) {
if(is(k.x dx[i], k.y dy[i])) {
v.push({k.x dx[i], k.y dy[i]});
b[k.x dx[i]][k.y dy[i]] = true;
a[k.x dx[i]][k.y dy[i]] = a[k.x][k.y] 1;
}
}
}
}
int main () {
int x, y;
cin >> n >> m >> x >> y;
--x;
--y;
b[x][y] = true;
bfs(x, y);
for (int i = 0; i < n; i) {
for (int j = 0; j < m; j) {
if (!b[i][j]) {
cout << -1 << " ";
continue;
}
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
