常德建设局官方网站,建设电商网站多少钱,dw如何发布网页,管理网站开发教程FloodFill和最短路 FloodFillAcwing 1097. 池塘计数AcWing 1098. 城堡问题AcWing 1106. 山峰和山谷 最短路AcWing 1076. 迷宫问题AcWing 188. 武士风度的牛AcWing 1100. 抓住那头牛 FloodFill
Acwing 1097. 池塘计数
//acwing 1097. 池塘计数
#include iostream
#inc… FloodFill和最短路 FloodFillAcwing 1097. 池塘计数AcWing 1098. 城堡问题AcWing 1106. 山峰和山谷 最短路AcWing 1076. 迷宫问题AcWing 188. 武士风度的牛AcWing 1100. 抓住那头牛 FloodFill
Acwing 1097. 池塘计数
//acwing 1097. 池塘计数
#include iostream
#include cstring
#include algorithm#define x first
#define y secondusing namespace std;typedef pairint, 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 3for (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 algorithmusing namespace std;typedef pairint, 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移动方格的同时配合二进制判断这个位置是否有墙//因此我们dxdy数组的定义就得按照题目给的来了西北东南这个顺序{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 iostreamusing namespace std;typedef pairint, 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 pairint, 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-1n-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 cstringusing namespace std;
typedef pairint, 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. 抓住那头牛
