P1443马的遍历 | Wuhaoda's Blog

P1443马的遍历

传送门:

https://www.luogu.org/problemnew/show/P1443

反思:

本来打算刷一道搜索水题练练手的
但是交了三次才过
思路是对了, 还是坑在了判重上
这次使用的是二元数组vis暴力判重
但是出现了死循环 oj上显示的是MLE
自己以为哪里数组什么的没开好 找了很久
其实是出现很多重复入栈行为 理所当然爆栈了
下次出现bug应多考虑考虑内因 不可盲目调试
死循环的原因是这一段:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
while(q.size()) {
temp = q.front(), q.pop();
nx = temp.x, ny = temp.y, nn = temp.num;
vis[nx][ny] = 1; //标记加在了这里
data[nx][ny] = nn;
For(i, 0, 7) {
lx = nx + step[i][0], ly = ny + step[i][1];
// cout<<lx<<" "<<ly<<"orz"<<endl;
if(lx < 1 || ly < 1 || lx > n || ly > m || vis[lx][ly])
continue;
// vis[lx][ly] = 1; //应该加在这里
temp.x = lx, temp.y = ly, temp.num = nn + 1;
q.push(temp);
}
}
}

画个图模拟一下就可找到原因:
x y z两两互通
假如X把Y Z 入栈了 (此时YZ不标记)
然后假如下一个是Y (Y现在标记了z还是没标记)
Y又把Z入栈 但是现在栈中有了两个Z
所以入栈前就应该把元素标记

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#define For(a, b, c) for(register int a = b; a <= c; ++a)
using namespace std;

struct pos {
int x, y, num;
};

int n, m, sx, sy, nx, ny, nn, lx, ly;
int data[401][401];
int vis[401][401];
int step[8][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
queue<pos> q;

inline void bfs() {
pos temp;
temp.x = sx, temp.y = sy, temp.num = 0;
data[sx][sy] = 0;
vis[sx][sy] = 1;
q.push(temp);
while(q.size()) {
temp = q.front(), q.pop();
nx = temp.x, ny = temp.y, nn = temp.num;
data[nx][ny] = nn;
For(i, 0, 7) {
lx = nx + step[i][0], ly = ny + step[i][1];
// cout<<lx<<" "<<ly<<"orz"<<endl;
if(lx < 1 || ly < 1 || lx > n || ly > m || vis[lx][ly])
continue;
temp.x = lx, temp.y = ly, temp.num = nn + 1;
vis[lx][ly] = 1;
q.push(temp);
}
}
}

inline void init() {
scanf("%d %d %d %d", &n, &m, &sx, &sy);
}

int main() {
int kkk = -1;
init();
bfs();
For(i, 1, n) {
For(j, 1, m)
if(data[i][j] != 0 || (i == sx && j == sy))
printf("%-5d", data[i][j]);
else
printf("%-5d", kkk);
printf("\n");
}
}