算法提高-搜索-FloodFill和最短路

FloodFill

Acwing 1097. 池塘计数

//acwing 1097. 池塘计数
#include <iostream>
#include <cstring>
#include <algorithm>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;
const int N = 1e3 + 10;
const int M = 1e3 + 10;
char g[N][M];
bool st[N][M];
PII q[N * M];
int n, m;void bfs (int sx, int sy)
{int hh = 0, tt = 0;q[0] = {sx, sy};st[sx][sy] = true;while (hh <= tt){PII t = q[hh ++ ];for (int i = t.x - 1; i <= t.x + 1 ; i ++ )for (int j = t. y - 1; j <= t.y + 1; j ++ ){if (i == t.x && j == t.y ) continue;//懒得用dx dy，直接遍历它周围9个地方把中间挖去，就是八个方向if (i < 0 || i >= n || j < 0 || j >= m) continue;//判断下标是否合法if (g[i][j] == '.' || st[i][j]) continue;//判断遍历的是否是水坑q[++ tt] = {i, j};st[i][j] = true;//作用是判断是否遍历过}}
}int main()
{int cnt = 0;cin >> n >> m;// for (int i = 0; i < n; i ++ )//     for (int j = 0; j < m; j ++ ) //         scanf ("%c", &g[i][j]); 算出来的cnt = 3；for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);for (int i = 0; i < n; i ++ )//遍历所有地图for (int j = 0; j < m; j ++ )if (g[i][j]  == 'W' && !st[i][j]){bfs(i, j);//找到一个没遍历过的水坑，用bfs将其扩展cnt ++ ;}cout << cnt ;    return 0;
}

AcWing 1098. 城堡问题

#include <iostream>
#include <algorithm>using namespace std;typedef pair<int, int> PII;
#define x first
#define y secondconst int N = 51, M = 51;
PII q[N * M];
int g[N][M];
bool st[N][M];int n, m;int bfs(int sx, int sy)
{int area = 0;//房间大小int hh = 0, tt = -1;q[++ tt ] = {sx, sy};int dx[4] = {0, -1, 0, 1};//上下左右四个方向int dy[4] = {-1, 0, 1, 0};while (hh <= tt){PII t = q[hh ++ ];st[t.x][t.y] = true;area ++ ;for (int i = 0; i <= 3; i ++ )//很精髓的地方，配合题意给的二进制，用一个for移动方格的同时配合二进制判断这个位置是否有墙//因此我们dx，dy数组的定义就得按照题目给的来了，西北东南这个顺序{int a = t.x + dx[i], b = t.y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m) continue;if (st[a][b]) continue;if (g[t.x][t.y] >> i & 1) continue;q[++ tt] = {a, b};st[a][b] = true;}}return area;
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i ++ ) for (int j = 0; j < m; j ++ )scanf ("%d", &g[i][j]);//这题目用的是二进制表示一个方格，不是直接字符串表示地图int cnt = 0;//房间数量int areaMax = 0;//房间大小for (int i = 0; i < n; i ++ )//1.找到房间，2.bfs的作用是扩展房间for (int j = 0; j < m; j ++ )if (!st[i][j])//判断每一个方格是否被遍历过，没有的话就BFS遍历{cnt ++ ;areaMax = max(areaMax, bfs(i, j));//多了一个房间大小，bfs的时候记录一下就行了}cout << cnt << endl << areaMax;return 0;
}

AcWing 1106. 山峰和山谷

这题不能在bfs的时候通过st[i][j]直接continue，否则会多计算peak或者valley，暂时没想到好的解释方法，只能说他为了判断边界，bfs扩展的一层内的每个点都要用来判断一下改山是否是山峰或者山谷，否则一个山可能既是山峰又是山谷，导致多计数了。

#include <iostream>using namespace std;typedef pair<int, int> PII;
#define x first
#define y second
const int N = 1e3 + 10;PII q[N * N];
int g[N][N];
bool st[N][N];int n;void bfs(int sx, int sy, bool& has_higher, bool& has_lower)
{int hh = 0, tt = -1;q[++ tt] = {sx, sy};while (hh <= tt){PII t = q[hh ++];st[t.x][t.y] = true;for (int i = t.x - 1; i <= t.x + 1; i ++ )for (int j = t.y - 1; j <= t.y + 1; j ++ ){if (i < 0 || i >= n || j < 0 || j >= n) continue;if (i == t.x && j == t.y) continue;//if (st[i][j]) continue; //不能直接跳过,因为需要重复使用这个联通块内的点来判断边界if (g[i][j] != g[t.x][t.y])//判断边界，是否是一片山脉{if(g[i][j] > g[t.x][t.y]) has_higher = true;//判断边界，//利用反向判断：是否连通块周围没有比他更高的或者更矮的else has_lower = true;}else if(!st[i][j]){st[i][j] = true;q[++ tt] = {i, j};}}}
}
int main()
{cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )scanf("%d", &g[i][j]);int peak = 0;int valley = 0;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ ){if (!st[i][j]){bool has_higher = false;bool has_lower = false;bfs(i, j, has_higher, has_lower);if (!has_higher) peak ++;if (!has_lower) valley ++;}}cout << peak << " " << valley;return 0;
}

最短路

AcWing 1076. 迷宫问题

#include <iostream>
#include <cstring>
using namespace std;typedef pair<int, int> PII;#define x first
#define y secondconst int N = 1e3 + 10;PII q[N * N];
int g[N][N];
PII pre[N][N];int n;void bfs(int sx, int sy)
{memset(pre, -1, sizeof pre);//pre里面是pair，这个会将pair的第一个值赋值为-1pre[n - 1][n - 1] = {100000, 100000};//因为是倒着bfs的，所以起点（n-1，n-1）的上一个点随便复制即可，防止它重复入队，浪费时间int dx[4] = {-1, 0, 1, 0};int dy[4] = {0, 1, 0, -1};int hh = 0, tt = -1;q[++ tt] = {sx, sy};while (hh <= tt){PII t = q[hh ++];for (int i = 0; i <= 3; i ++ ){int a = t.x + dx[i], b = t.y + dy[i];if (a < 0 || a >= n || b < 0 || b >= n) continue;if (pre[a][b].x != -1) continue;//pre也起到了一个st数组的作用，判断当前这个点是否到达过了，因为第一次到达才是最短的if (!g[a][b]) //非1可以走{pre[a][b] = t;q[++ tt] = {a, b};}}}
}int main()
{cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )scanf("%d", &g[i][j]);bfs(n - 1, n - 1);PII end = {0, 0};while (true)//这个倒序打印挺经典的{printf("%d %d\n", end.x, end.y);if (end.x == n - 1 && end.y == n - 1) break;//如果打印到终点 n - 1 n -1了就退出循环end = pre[end.x][end.y];}return 0;
}

AcWing 188. 武士风度的牛

#include <iostream>
#include <cstring>using namespace std;
typedef pair<int, int> PII;
#define x first
#define y secondconst int N = 150 + 10;char g[N][N];
PII q[N * N];
int dist[N][N];
int n, m;int bfs()
{int dx[8] = {1, 2, -1, -2, -2, -1, 1, 2};int dy[8] = {-2, -1, -2, -1, 1, 2, 2, 1};int sx, sy;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )if (g[i][j] == 'K')sx = i, sy = j;memset(dist, -1, sizeof dist);//省去一个st数组int hh = 0, tt = -1;q[++ tt] = {sx, sy};dist[sx][sy] = 0;//自己到自己的距离为0while (hh <= tt){PII t = q[hh ++];for (int i = 0; i <= 7; i ++ ){int a = t.x + dx[i], b = t.y + dy[i];if (a < 0 || a >= n || b < 0 || b >= m) continue;if (g[a][b] == '*') continue;if (dist[a][b] != -1) continue;if (g[a][b] == 'H') return dist[t.x][t.y] + 1;dist[a][b] = dist[t.x][t.y] + 1;q[++ tt] = {a, b};}}
}int main()
{cin >> n >> m;for (int i = 0; i < n; i ++ ) cin >> g[i];cout << bfs();return 0;}

AcWing 1100. 抓住那头牛