lyd读书笔记 宽搜(1)朴素宽搜

因为宽搜码农大题真的特别多所以。。不得不过的松一点否则就GG了

基础宽搜

我们从队头取出状态,然后对所有分支,将每条分支到达的下一个状态插入队尾。

POJ3322

码农大题。。

过分复杂,lazytag。

BZOJ2252 矩阵距离

一开始看错题了。。题干的意思是求矩阵内所有点到点1的最短距离,也就是flood-fill。

flood-fill模型既可以用dfs解,也可以用BFS解。这里其实是一个普通的多起点问题。

全扔进去跑一遍BFS即可。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <queue>
#include <cstring>

using namespace std;

inline void out(int x) {
if(x < 0) putchar('-'), x = -x;
if(x > 9) out(x / 10);
putchar(x % 10 + '0');
}

inline void read(int& x) {
x = 0; char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
}

int n, m;
string tmp;
char mar01[1003][1003];
int dis[1003][1003];

#define pii pair<int, int>
#define X first
#define Y second

queue<pii> q;

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

inline bool can(int x, int y, int type) {
if(x + dx[type] < 1) return false;
if(x + dx[type] > n) return false;
if(y + dy[type] < 1) return false;
if(y + dy[type] > m) return false;
if(dis[x + dx[type]][y + dy[type]] != -1) return false;
return true;
}

int main() {
read(n), read(m);
memset(dis, -1, sizeof dis);
for(int i = 1; i <= n; ++i) {
cin>>tmp;
for(int j = 1; j <= m; ++j) {
mar01[i][j] = tmp[j - 1] - '0';
if(mar01[i][j] == 1) q.push(pii(i, j)), dis[i][j] = 0;
}
}
/*for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j)
out(mar01[i][j]), putchar(' ');
puts("");
}*/
while(!q.empty()) {
pii tmp = q.front();
q.pop();
for(int i = 0; i < 4; ++i) {
if(can(tmp.X, tmp.Y, i))
q.push(pii(tmp.X + dx[i], tmp.Y + dy[i])),
dis[tmp.X + dx[i]][tmp.Y + dy[i]] = dis[tmp.X][tmp.Y] + 1;
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= m; ++j)
out(dis[i][j]), putchar(' ');
puts("");
}

return 0;
}

/*
3 4
0001
0011
0110
*/

POJ1475 推箱子

嗯。。思想很妙妙,就是太码农…如果之后有时间再回来写吧

这种东西叫做双重BFS。考虑到推前的人和箱子一定是紧紧捆绑在一起的,因此我们用状态$(x, y, type)(type \in [0, 3])$表示在$(x, y)$时的状态。

我们考虑到,如果人不存在,箱子的位置变化是显然可以BFS出来的。然后就是,对于人来说,达到让箱子能走的下一步,这个过程可以通过一个BFS出来。

换言之,我们进行了一个BFS套BFS的工作。总复杂度不超过$O(n^2m^2)$。

具体似乎有些细节要注意的样子。。

最后是输出方案的问题,我们记录出箱子的路径然后再逆推一遍人的轨迹即可。

Author

LittleRewriter

Posted on

2018-02-26

Updated on

2021-07-28

Licensed under

Comments