✔Flood Fill

AcWing 1097. 池塘计数

DFS

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
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;
char f[N][N];

void dfs(int x, int y)
{
//枚举周围八个格子
for (int i = x - 1; i <= x + 1; i++)
for (int j = y - 1; j <= y + 1; j++)
if (f[i][j] == 'W')
{
f[i][j] = '.';
dfs(i, j);
}
}

int main()
{
int n, m;
scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i++)
scanf("%s", f[i] + 1); //下标从1开始可解决边境问题

int ans = 0; //池塘数目
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (f[i][j] == 'W')
{
dfs(i, j);
ans++;
}

printf("%d", ans);

return 0;
}

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
#include<iostream>
#include<queue>
#define x first
#define y second
using namespace std;

const int N = 1010;
char mp[N][N];
bool st[N][N];
int cnt;
int n, m;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

typedef pair<int, int> PII;

void bfs(int x, int y)
{
queue<PII> q;
q.push({x, y});

while(q.size())
{
auto t = q.front();
q.pop();

for(int i = 0; i < 8; i ++){
int nx = t.x+dx[i], ny = t.y+dy[i];
if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if(mp[nx][ny] == '.' || st[nx][ny]) continue;
q.push({nx, ny});
mp[nx][ny] = '.';
st[nx][ny] = true;
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++) scanf("%s", mp[i]);;

for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
if(mp[i][j]=='W'){
cnt ++;
bfs(i, j);
}
}
}
printf("%d", cnt);
return 0;
}

[AcWing 1098. 城堡问题](1098. 城堡问题 - AcWing题库)

对墙的描述新颖(用一个数就形容了周围一圈位置[不包括当前]中是否为墙), 可以应用位运算

话说这种构造和我练习的一个构建迷宫的方式有点像

[python实现] 递归回溯(深度优先)构造随机迷宫_泥烟的博客-CSDN博客

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
#include<iostream>
#define x first
#define y second
using namespace std;

const int N = 55;
typedef pair<int, int> PII;
int n, m;
int num, maxArea;
int mp[N][N];
bool st[N][N];
PII q[N*N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

int bfs(int x, int y)
{
int front = 0, rear = 0;
q[++rear] = {x, y};
st[x][y] = true;

while(front != rear)
{
PII t = q[++front];

for(int i = 0; i < 4; i ++){
int nx = t.x+dx[i], ny = t.y+dy[i];
if(!nx || !ny || nx > n || ny > m) continue;
if(st[nx][ny]) continue;
if(mp[t.x][t.y] >> i & 1) continue; //该方向有墙
q[++rear] = {nx, ny};
st[nx][ny] = true;
}
}
return front; //front游标间接代表了出队的数量
}
int main()
{
cin >> n >> m;

for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
cin >> mp[i][j];

for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
{
if(!st[i][j]){
num ++;
maxArea = max(maxArea, bfs(i, j));
}
}
cout << num << '\n' << maxArea;
return 0;
}

AcWing 1106. 山峰和山谷

需判断当前位置是否为极值点

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
#include<iostream>
#define x first
#define y second
using namespace std;

const int N = 1010;
int n;
int h[N][N];
int cntH, cntD;
int dx[8]={-1, -1, -1, 0, 0, 1, 1, 1},dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
bool st[N][N];
typedef pair<int, int> PII;
PII p[N*N];

void bfs(int x, int y, int w)
{
int isH = 1, isD = 1;
int front = 0, rear = 0;
p[++rear] = {x, y};
while(front != rear)
{
PII t = p[++front];
for(int i = 0; i < 8; i ++)
{
int nx = t.x+dx[i], ny = t.y+dy[i];
if(!nx || !ny || nx>n || ny>n) continue;
if(h[nx][ny] != w){ //高度不同时, 山峰or山谷的判断更新
isH &= (h[nx][ny]<w);
isD &= (h[nx][ny]>w);
continue ;
}
if(st[nx][ny]) continue;
p[++rear] = {nx, ny};
st[nx][ny] = true;
}
}
cntH += isH;
cntD += isD;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j++)
scanf("%d", &h[i][j]);

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(!st[i][j]) bfs(i, j, h[i][j]);
}
}
printf("%d %d", cntH, cntD);
return 0;
}

✔最短路模型

AcWing 1076. 迷宫问题

💡也可以从终点往回搜, 这样就不用递归了

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<cstring>
#define x first
#define y second
using namespace std;

const int N = 1010;
typedef pair<int, int> PII;
int n;
int num, maxArea;
int mp[N][N];
PII q[N*N];
PII pre[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {-1, 0, 1, 0};

inline void bfs(int x, int y)
{
memset(pre, -1, sizeof pre);
int front = 0, rear = 0;
q[++rear] = {x, y};
pre[x][y] = {0, 0};

while(front != rear)
{
PII t = q[++front];
for(int i = 0; i < 4; i ++){
int nx = t.x+dx[i], ny = t.y+dy[i];
if(nx<0 || ny<0 || nx>=n || ny>=n) continue;
if(mp[nx][ny]) continue;
if(pre[nx][ny].x != -1) continue; //前驱不是{-1, -1},说明已经访问过

q[++rear] = {nx, ny};
pre[nx][ny] = t;
if(nx == n-1 && ny == n-1) return;
}
}
}
inline void dfsPath(int a, int b) //递归输出正向路线
{
if(!a && !b) printf("0 0\n");
else{
dfsPath(pre[a][b].x, pre[a][b].y);
printf("%d %d\n", a, b);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &mp[i][j]);

bfs(0, 0);
dfsPath(n-1, n-1);
return 0;
}

AcWing 188. 武士风度的牛

走”日”, 注意边界

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
// 人傻掉, 以后判断边界尽量不用 !nx, !ny
// 比如这道题就可能越界好几个单位

#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;

const int N = 155;
char mp[N][N];
int step[N][N];
int n, m;
int dx[8]={-2, -2, -1, 1, 2, 2, 1, -1};
int dy[8]={-1, 1, 2, 2, 1,-1, -2,-2};
typedef pair<int, int> PII;
PII p[N*N];

int bfs(int x, int y)
{
memset(step, -1, sizeof(step));
int front = 0, rear = 0;
p[++rear] = {x, y};
step[x][y] = 0;
while (front != rear)
{
PII t = p[++front];

for(int i = 0; i < 8; i ++)
{
int nx = t.x+dx[i], ny = t.y+dy[i];
if(nx<1 || ny<1 || nx>n || ny>m) continue;
if(mp[nx][ny]=='*' || step[nx][ny]!=-1) continue;
if(mp[nx][ny]=='H') return step[t.x][t.y]+1;

p[++rear] = {nx, ny};
step[nx][ny] = step[t.x][t.y]+1;
}
}
return -1;
}
int main()
{
scanf("%d%d", &m, &n);
for(int i = 1; i <= n; i ++) scanf("%s", mp[i]+1);

for(int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j++) {
if(mp[i][j]=='K'){
printf("%d", bfs(i, j));
return 0;
}
}

return 0;
}

AcWing 1100. 抓住那头牛

“一维”走迷宫

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
#include<iostream>
#include<cstring>
using namespace std;

const int N = 1e5+10;
int n, k;
int q[N];
int dist[N];

int bfs()
{
memset(dist, -1, sizeof(dist));
int front = 0, rear = 0;
q[++rear] = n;
dist[n] = 0;

while(front != rear)
{
int t = q[++front];
if(t == k) return dist[k];
if(t + 1 <= k && dist[t+1]==-1) q[++rear]=t+1, dist[t+1]=dist[t]+1;
if(t - 1 >= 0 && dist[t-1]==-1) q[++rear]=t-1, dist[t-1]=dist[t]+1;
if((t<<1) <= k+1 && dist[t<<1]==-1) q[++rear]=t<<1, dist[t<<1]=dist[t]+1;
}
}
int main()
{
cin >> n >> k;
cout << bfs();
return 0;
}

“(t<<1) <= k+1”

t * 2 一旦比 k 多了2个及以上 ,我们就可以先减再乘


✔多源BFS

AcWing 173. 矩阵距离

被第一次更新时,即为最终求得的最小距离

这一点和Dijkstra的堆优化版本的区别在于, Dijkstra出队时为最终求得的最小距离(即第一次入队时未必是最优)

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
#include <cstring>
#include <iostream>
#define x first
#define y second
using namespace std;

const int N = 1010;
typedef pair<int, int> PII;
int n, m;
char g[N][N];
int dist[N][N];
PII q[N*N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs()
{
memset(dist, -1, sizeof dist);

int front = 0, rear = 0;
// 把1看作第一层, 从 1 开始搜
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
if (g[i][j] == '1')
{
dist[i][j] = 0;
q[++rear] = {i, j};
}

while (front != rear)
{
PII t = q[++front];

for (int i = 0; i < 4; i ++ )
{
int a = t.x + dx[i], b = t.y + dy[i];
if (!a || !b || a > n || b > m) continue;
//距离已被更新(此时dist[a][b]便是该点最短的0-1距离)
if (dist[a][b] != -1) continue;

dist[a][b] = dist[t.x][t.y] + 1;
q[++rear] = {a, b};
}
}
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ) scanf("%s", g[i]+1);

bfs();

for (int i = 1; i <= n; i ++ )
{
for (int j = 1; j <= m; j ++ ) printf("%d ", dist[i][j]);
printf("\n");
}

return 0;
}


✔最小步数模型

AcWing 1107. 魔板

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
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<unordered_map>
using namespace std;

//char g[2][4];
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;

string turn(string s, int x)
{
if (x == 0) return {s[7], s[6], s[5], s[4], s[3], s[2], s[1], s[0]};
else if (x == 1) return {s[3], s[0], s[1], s[2], s[5], s[6], s[7], s[4]};
else if (x == 2) return {s[0], s[6], s[1], s[3], s[4], s[2], s[5], s[7]};
}

int bfs(string start, string end)
{
if(start == end) return 0;
queue<string> q;
q.push(start);
dist[start] = 0;

while(q.size())
{
string t = q.front();
q.pop();

for(int i = 0; i < 3; i ++)
{
string op = turn(t, i);
if(dist.count(op)==0)
{
q.push(op);
dist[op] = dist[t]+1;
pre[op] = {char(i+'A'), t}; //记录步骤
if(op == end) return dist[end];
}
}
}

return -1;
}
// 递归,正向输出步骤
void dfs(string s, string start){
if(s == start){
return ;
}else{
dfs(pre[s].second, start);
cout << pre[s].first;
}
}
int main()
{
ios_base::sync_with_stdio(false);
int x;
string start, end;
for(int i = 1; i <= 8; i ++){
cin >> x;
end += char(x+'0');
start += char(i+'0');
}

int step = bfs(start, end);
cout << step << '\n';
dfs(end, start);
return 0;
}

双端队列广搜

AcWing 175. 电路维修


双向广搜

AcWing 190. 字串变换


A*

AcWing 178. 第K短路

AcWing 179. 八数码


DFS之连通性模型

AcWing 1112. 迷宫

AcWing 1113. 红与黑


DFS之搜索顺序

AcWing 1116. 马走日

AcWing 1117. 单词接龙

AcWing 1118. 分成互质组


DFS之剪枝与优化

AcWing 165. 小猫爬山

AcWing 166. 数独

AcWing 167. 木棒

AcWing 168. 生日蛋糕


迭代加深

AcWing 170. 加成序列


双向DFS

AcWing 171. 送礼物


IDA*

AcWing 180. 排书

AcWing 181. 回转游戏