服了 bfs板子题
我一直在那想该怎么解决重复搜索路径覆盖的问题,开个bool数组不就完了吗,搜过的不搜了不就行了,第一次搜到的肯定是距离最短的,这题要用bfs
什么时候用dfs 什么时候用bfs
我现在得出的经验是 让你求路径 求最短路用bfs 反正要你记下你走了多少步就要用bfs
dfs一般就是用来求方案数 问你有多少种组合一般就用 dfs
马的遍历
题目描述
有一个 $n \times m$ 的棋盘,在某个点 $(x, y)$ 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
输入只有一行四个整数,分别为 $n, m, x, y$。
输出格式
一个 $n \times m$ 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 $-1$)。
样例 #1
样例输入 #1
3 3 1 1
样例输出 #1
0 3 2
3 -1 1
2 1 4
提示
数据规模与约定
对于全部的测试点,保证 $1 \leq x \leq n \leq 400$,$1 \leq y \leq m \leq 400$。
题解
考试这种题知道了方法应该能做出来 纯粹的板子题 应该是掌握了 明天练练手
#include <bits/stdc++.h>
using namespace std;
const int N = 410;
typedef pair<int, int> PII;
int n, m, x, y;
bool st[N][N];
int dx[8] = {-1, -2, -2, -1, 1, 2, 2, 1}, dy[8] = {2, 1, -1, -2, -2, -1, 1, 2}; //枚举马一步之内能走到的点
int g[N][N];
void solve()
{
scanf("%d%d%d%d", &n, &m, &x, &y);
queue<PII> q;
q.push({x, y});
st[x][y] = true; //标记已经走过
g[x][y] = 0;
while (q.size())
{
auto t = q.front();
int a = t.first, b = t.second;
q.pop();
for (int i = 0; i < 8; i ++ )
{
int l, r;
l = a + dx[i], r = b + dy[i]; //枚举可能走到的点
if (l > 0 && l <= n && r > 0 && r <= m && !st[l][r])
{
g[l][r] = g[a][b] + 1;
st[l][r] = true;
q.push({l, r});
}
}
}
for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ )
{
if (st[i][j])
{
printf("%d ", g[i][j]);
}
else printf("-1 ");
}
cout << endl;
}
return;
}
int main()
{
solve();
return 0;
}