广度优先搜索
洛谷P1443
这里先介绍一下广度优先搜索：
广度优先搜索就是先将第一步可能的步骤全部记录，遍历过后，再将由第一步到达的第二步全部记录并遍历，直到最后全部遍历。
而此题要求我们求得最少步数，广度优先就能够达到最少步数的要求，因为广度优先是先通过搜索所有可能的第n步才进行第n+1步
这里还涉及到bfs的超时问题，后面会细说
广度优先遍历模板
void bfd(){
q.push(初始状态);
while(!q.empty()) {
STATE u = q.front(); // 记录目前的状态
for(目前状态能达到的下一步){
if(v未被未访问过){
q.push(v)；
}
}
}
}
那其实用这个模板就已经足够解决这个问题了
下面就是半成品代码（为啥不是成品）
#include<bits/stdc++.h>
using namespace std;
struct pos{
int x, y;
int now;
};
queue<pos> q;
int direct[8][2] = {{2,1}, {1,2}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2}};
int n, m, x_0, y_0;
int ans[405][405];
bool check(int i, int x, int y) {
if(direct[i][0] + x > n || direct[i][1] + y > m) return false;
if(direct[i][0] + x < 1 || direct[i][1] + y < 1) return false;
return true;
}
int main() {
memset(ans, -1, sizeof(ans));
cin >> n >> m >> x_0 >> y_0;
struct pos primary;
primary.x = x_0; primary.y = y_0; primary.now = 0;
q.push(primary);
while(!q.empty()) {
int ux = q.front().x;
int uy = q.front().y;
int unow = q.front().now;
ans[ux][uy] = unow;
for(int i = 0; i < 8; i++) {
if(check(i, ux, uy) && ans[ux+direct[i][0]][uy+direct[i][1]] == -1) {
struct pos temp;
temp.x = ux+direct[i][0]; temp.y = uy+direct[i][1];
temp.now = unow + 1;
q.push(temp);
}
}
q.pop();
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
printf("%-5d", ans[i][j]);
}
printf("\n");
}
system("pause");
}
超时问题
上面的代码可以解决一些数据小的用例，但是数据过大就会超时（我就过了两个用例）
那为啥会超时呢
很容易想到，超时一般是遍历重复导致的（枚举是重复最多的）
有人可能会说，上面代码中if(check(i, ux, uy) && ans[ux+direct[i][0]][uy+direct[i][1]] == -1)不是已经有了判断重复吗
那我们想一下这种情况，3×3的棋盘，从（1，1）开始
| 0 | xx | xx |
| xx | xx | xx |
| xx | xx | xx |
有两个位置可走
| 0 | xx | xx |
| xx | xx | 1 |
| xx | 1 | xx |
第三行第二列（3，2）遍历到这里时，可以走到（1，1）这个位置，但由于已经ans[1][1]已经被赋值0，所以没有把（1，1）增加到队列中
第二行第三列（2，3）遍历到这里时，可以走到（1，1）这个位置，但由于已经ans[1][1]已经被赋值0，所以没有把（1，1）增加到队列中
这就是 ans[ux+direct[i][0]][uy+direct[i][1]] == -1限制条件的作用，但我们想另一种情况
| xx | xx | xx | xx | xx |
| xx | xx | xx | xx | xx |
| xx | xx | 1 | xx | xx |
| 0 | xx | xx | xx | YYYY |
| xx | xx | 2 | xx | xx |
| xx | xx | xx | xx | xx |
| xx | xx | xx | xx | xx |
1和2为同一层，即步数相等，这里的1和2都能走到YYYY这个位置，先遍历1，然后将其能够达到的下一步（1的下一步）加入队列中，再遍历2，然后将其能够达到的下一步（2的下一步）加入队列中
这时我们队列中就是 1 2（1的下一步）（2的下一步）这四部分
但是我们想一想，YYYY是否同时在（1的下一步）和（2的下一步）呢，答案是在。
YYYY还没被遍历到，也就是它的ans还未赋值，2的下一步遍历就已经把它加入到队列中了，虽然不会有二次赋值，但会增加搜索空间，如果数据足够大，就会有很多搜索重复，所以我们需要增加一个是否已经被加入队列的判断（增加了一个flag二维数组）。
下面就是AC代码
#include<bits/stdc++.h>
using namespace std;
struct pos{
int x, y;
int now;
};
queue<pos> q;
int direct[8][2] = {{2,1}, {1,2}, {2,-1}, {1,-2}, {-1,-2}, {-2,-1}, {-2,1}, {-1,2}};
int n, m, x_0, y_0;
int ans[405][405],flag[405][405];
bool check(int i, int x, int y) {
if(direct[i][0] + x > n || direct[i][1] + y > m) return false;
if(direct[i][0] + x < 1 || direct[i][1] + y < 1) return false;
return true;
}
int main() {
memset(ans, -1, sizeof(ans));
memset(flag, 0, sizeof(flag));
cin >> n >> m >> x_0 >> y_0;
struct pos primary;
primary.x = x_0; primary.y = y_0; primary.now = 0;
q.push(primary);
while(!q.empty()) {
int ux = q.front().x;
int uy = q.front().y;
int unow = q.front().now;
ans[ux][uy] = unow;
for(int i = 0; i < 8; i++) {
if(check(i, ux, uy) && ans[ux+direct[i][0]][uy+direct[i][1]] == -1 && !flag[ux+direct[i][0]][uy+direct[i][1]]) {
struct pos temp;
temp.x = ux+direct[i][0]; temp.y = uy+direct[i][1];
flag[temp.x][temp.y] = 1;
temp.now = unow + 1;
q.push(temp);
}
}
q.pop();
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
printf("%-5d", ans[i][j]);
}
printf("\n");
}
system("pause");
}