页面精美的网站,十堰微网站建设电话,网站建设及优化 赣icp,网站建设优秀网目录 引言一、池塘计数二、城堡问题三、山峰和山谷四、迷宫问题五、武士风度的牛六、抓住那头牛七、矩阵距离八、魔板 引言
针对于蓝桥杯#xff0c;搜索问题还是非常之重要的#xff0c;在省赛前深知暴搜的重要性#xff0c;所以提前先把提高课的搜索一章给看了#xff0… 目录 引言一、池塘计数二、城堡问题三、山峰和山谷四、迷宫问题五、武士风度的牛六、抓住那头牛七、矩阵距离八、魔板 引言
针对于蓝桥杯搜索问题还是非常之重要的在省赛前深知暴搜的重要性所以提前先把提高课的搜索一章给看了结果省赛时用到的算法很少几乎是没有反而是刚学一两个星期的暴搜给了我很大的作用全部题目几乎都用的是暴搜所以对于 O I OI OI 赛制来说暴搜的技巧还是很重要的其实到了国赛也是很重要听说国赛题都很难而且有的题都是假题所以说对于这种题暴搜就显得更重要了听说全打暴力就能国三再对个一两道题目说不定就能国二其实暴搜大部分样例跟全做出来没啥区别只要你剪枝剪的好就能多对几个样例还是要多练加油 一、池塘计数
标签BFS、Flood Fill
思路其实就是一个找连通块的题目只不过是一个八连通的把 B F S BFS BFS 里的循环和方向变为对应的八个方向即可。具体的做法就是遍历每一个格子如果该格子没有被访问过并且是一个池塘就用 B F S BFS BFS 把这个池塘全部访问然后结果加一最后输出结果。
题目描述
农夫约翰有一片 N∗M 的矩形土地。最近由于降雨的原因部分土地被水淹没了。现在用一个字符矩阵来表示他的土地。每个单元格内如果包含雨水则用”W”表示如果不含雨水则用”.”表示。现在约翰想知道他的土地中形成了多少片池塘。每组相连的积水单元格集合可以看作是一片池塘。每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。请你输出共有多少片池塘即矩阵中共有多少片相连的”W”块。输入格式
第一行包含两个整数 N 和 M。接下来 N 行每行包含 M 个字符字符为”W”或”.”用以表示矩形土地的积水状况字符之间没有空格。输出格式
输出一个整数表示池塘数目。数据范围
1≤N,M≤1000
输入样例
10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.
输出样例
3示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010, M N, INF 0x3f3f3f3f;int n, m;
char g[N][N];
bool st[N][N];int dir[8][2] {-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1};void bfs(PII S)
{st[S.x][S.y] true;queuePII q; q.push(S);while(q.size()){auto t q.front(); q.pop();for(int i 0; i 8; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y m) continue;if(st[x][y] || g[x][y] .) continue;st[x][y] true;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 0; i n; i) cin g[i];int res 0;for(int i 0; i n; i){for(int j 0; j m; j){if(!st[i][j] g[i][j] W){res;bfs({i,j});}}}cout res endl;return 0;
}二、城堡问题
标签BFS
思路这道题要求的是连通块的个数以及连通块中最大的那个。不一样的是该题的限制变成了每一个房间都会有墙也就是说能不能向某一个方向移动就看该方向是否有墙一般这种拿数字代表墙的都是二进制位来表示的只要把对应方向和该二进制位对应起来拿位运算就知道该方向是否有墙然后就是正常操作了每找一个点就给该连通块数加一返回总数即可。
题目描述 1 2 3 4 5 6 7 #############################1 # | # | # | | ######---#####---#---#####---#2 # # | # # # # ##---#####---#####---#####---#3 # | | # # # # ##---#########---#####---#---#4 # # | | | | # ##############################(图 1)# Wall | No wall- No wall方向上北下南左西右东。
图1是一个城堡的地形图。请你编写一个程序计算城堡一共有多少房间最大的房间有多大。城堡被分割成 m∗n个方格区域每个方格区域可以有0~4面墙。注意墙体厚度忽略不计。输入格式
第一行包含两个整数 m 和 n分别表示城堡南北方向的长度和东西方向的长度。接下来 m 行每行包含 n 个整数每个整数都表示平面图对应位置的方块的墙的特征。每个方块中墙的特征由数字 P 来描述我们用1表示西墙2表示北墙4表示东墙8表示南墙P 为该方块包含墙的数字之和。例如如果一个方块的 P 为3则 3 1 2该方块包含西墙和北墙。城堡的内墙被计算两次方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。输出格式
共两行第一行输出房间总数第二行输出最大房间的面积方块数。数据范围
1≤m,n≤50,0≤P≤15
输入样例
4 7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13
输出样例
5
9示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 55, M N, INF 0x3f3f3f3f;int n, m;
int g[N][N];
bool st[N][N];int dir[4][2] {0,-1, -1,0, 0,1, 1,0}; // 对应方向 int bfs(PII S) // 找出每个连通块内的块数
{st[S.x][S.y] true;int res 1;queuePII q; q.push(S);while(q.size()){auto t q.front(); q.pop();for(int i 0; i 4; i){// 注意这里是从 t 走的if(g[t.x][t.y] i 1) continue; // 刚好用与运算与之对应方向int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y m) continue;if(st[x][y]) continue;res;st[x][y] true;q.push({x,y}); } }return res;
} int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m; // 不要被变量名所骗要看具体含义for(int i 0; i n; i){for(int j 0; j m; j){cin g[i][j];}}int sum 0, maxv 0;for(int i 0; i n; i){for(int j 0; j m; j){if(!st[i][j]){int t bfs({i,j});sum;maxv max(maxv, t);}}}cout sum endl maxv endl;return 0;
}三、山峰和山谷
标签BFS、Flood Fill
思路这道题问山峰和山谷的数量其实就是遍历每一个连通块高度相同然后遍历的同时看看周围有没有比它更高的或者更低的如果没有比他高的那就是山峰如果没有比它低的那就是山谷如果两个都没有那就都是刚好也满足题目的要求。有一个细节就是判断的是周围所以只要不越界就都要判断一下所以不必先判断是否能走应最后判断。
题目描述
FGD小朋友特别喜欢爬山在爬山的时候他就在研究山峰和山谷。为了能够对旅程有一个安排他想知道山峰和山谷的数量。给定一个地图为FGD想要旅行的区域地图被分为 n×n 的网格每个格子 (i,j) 的高度 w(i,j) 是给定的。若两个格子有公共顶点那么它们就是相邻的格子如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j1),(i,j−1),(i,j1)(i1,j−1)
,(i1,j),(i1,j1)。我们定义一个格子的集合 S 为山峰山谷当且仅当S 的所有格子都有相同的高度。S 的所有格子都连通。对于 s 属于 S与 s 相邻的 s′ 不属于 S都有 wsws′山峰或者 wsws′山谷。如果周围不存在相邻区域则同时将其视为山峰和山谷。你的任务是对于给定的地图求出山峰和山谷的数量如果所有格子都有相同的高度那么整个地图即是山峰又是山谷。输入格式
第一行包含一个正整数 n表示地图的大小。接下来一个 n×n 的矩阵表示地图上每个格子的高度 w。输出格式
共一行包含两个整数表示山峰和山谷的数量。数据范围
1≤n≤1000,0≤w≤109
输入样例1
5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8
输出样例1
2 1
输入样例2
5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7
输出样例2
3 3示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010, M N, INF 0x3f3f3f3f;int n, m;
int g[N][N];
bool st[N][N];
int high, low;int dir[8][2] {-1,-1, -1,0, -1,1, 0,-1, 0,1, 1,-1, 1,0, 1,1};void bfs(PII S)
{st[S.x][S.y] true;bool has_higher false, has_lower false;queuePII q; q.push(S);while(q.size()){auto t q.front(); q.pop();for(int i 0; i 8; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y n) continue; // 先判断是否越界if(g[x][y] g[t.x][t.y]) has_higher true; // 判断周围if(g[x][y] g[t.x][t.y]) has_lower true;if(st[x][y] || g[x][y] ! g[t.x][t.y]) continue; // 判断是否为连通块st[x][y] true;q.push({x,y});}}if(!has_higher) high; // 没有比它高的if(!has_lower) low; // 没有比他低的
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i){for(int j 0; j n; j){cin g[i][j];}}for(int i 0; i n; i){for(int j 0; j n; j){if(!st[i][j]){bfs({i,j});}}}cout high low endl;return 0;
}四、迷宫问题
标签BFS
思路这道题问的是一个最短的路径其实针对于 B F S BFS BFS 来说第一次走过的点就是该点的最短路径我们只要在遍历的时候把要更新的点的前驱记下来即可。因为路径是从起点开始我们可以直接从后向前遍历这样在推导的时候就可以顺便打印了。
题目描述
给定一个 n×n 的二维数组如下所示int maze[5][5] {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};
它表示一个迷宫其中的1表示墙壁0表示可以走的路只能横着走或竖着走不能斜着走要求编程序找出从左上角到右下角
的最短路线。数据保证至少存在一条从左上角走到右下角的路径。输入格式
第一行包含整数 n。接下来 n 行每行包含 n 个整数 0 或 1表示迷宫。输出格式
输出从左上角到右下角的最短路线如果答案不唯一输出任意一条路径均可。按顺序每行输出一个路径中经过的单元格的坐标左上角坐标为 (0,0)右下角坐标为 (n−1,n−1)。数据范围
0≤n≤1000
输入样例
5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
输出样例
0 0
1 0
2 0
2 1
2 2
2 3
2 4
3 4
4 4示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010, M N, INF 0x3f3f3f3f;int n, m;
int g[N][N];
bool st[N][N];
PII pre[N][N]; int dir[4][2] {0,1,0,-1,1,0,-1,0};void bfs()
{st[n-1][n-1] true;queuePII q; q.push({n-1,n-1});while(q.size()){auto t q.front(); q.pop();if(t.x 0 t.y 0) return;for(int i 0; i 4; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y n) continue;if(st[x][y] || g[x][y] 1) continue;st[x][y] true;pre[x][y] {t.x,t.y};q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;for(int i 0; i n; i){for(int j 0; j n; j){cin g[i][j];}}bfs();PII start {0,0}, end {n-1,n-1};while(start ! end){cout start.x start.y endl;start pre[start.x][start.y];}cout end.x end.y endl;return 0;
}五、武士风度的牛
标签搜索、广度优先搜索、BFS
思路这道题首先要看清楚行列不一定是按顺序给你的所以要小心然后就是只不过搜索的时候把方式变了其实本质上还是行列的一个变化而已然后就是正常的求最短路。
最短路注意要点 1. 输入的行列顺序 2. 起始点有时就是障碍 3. 起点有时是终点 4. 终点的符号跟正常的符号不一样
题目描述
农民 John 有很多牛他想交易其中一头被 Don 称为 The Knight 的牛。这头牛有一个独一无二的超能力在农场里像 Knight 一样地跳就是我们熟悉的象棋中马的走法。虽然这头神奇的牛不能跳到树上和石头上但是它可以在牧场上随意跳我们把牧场用一个 xy 的坐标图来表示。这头神奇的牛像其它牛一样喜欢吃草给你一张地图上面标注了 The Knight 的开始位置树、灌木、石头以及其它障碍的位置
除此之外还有一捆草。现在你的任务是确定 The Knight 要想吃到草至少需要跳多少次。The Knight 的位置用 K 来标记障碍的位置用 * 来标记草的位置用 H 来标记。这里有一个地图的例子11 | . . . . . . . . . .10 | . . . . * . . . . . 9 | . . . . . . . . . . 8 | . . . * . * . . . . 7 | . . . . . . . * . . 6 | . . * . . * . . . H 5 | * . . . . . . . . . 4 | . . . * . . . * . . 3 | . K . . . . . . . . 2 | . . . * . . . . . * 1 | . . * . . . . * . . 0 ----------------------1 0 1 2 3 4 5 6 7 8 9 0
The Knight 可以按照下图中的 A,B,C,D… 这条路径用 5 次跳到草的地方有可能其它路线的长度也是 511 | . . . . . . . . . .10 | . . . . * . . . . .9 | . . . . . . . . . .8 | . . . * . * . . . .7 | . . . . . . . * . .6 | . . * . . * . . . F5 | * . B . . . . . . .4 | . . . * C . . * E .3 | .A . . . . D . . .2 | . . . * . . . . . *1 | . . * . . . . * . .0 ----------------------10 1 2 3 4 5 6 7 8 9 0
注意 数据保证一定有解。输入格式
第 1 行 两个数表示农场的列数 C 和行数 R。第 2..R1 行: 每行一个由 C 个字符组成的字符串共同描绘出牧场地图。输出格式
一个整数表示跳跃的最小次数。数据范围
1≤R,C≤150
输入样例
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..
输出样例
5示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 155, M N, INF 0x3f3f3f3f;int n, m;
char g[N][N];
int dist[N][N];
PII S, E;int dir[8][2] {-2,-1, -2,1, -1,-2, -1,2, 1,-2, 1,2, 2,-1, 2,1};int bfs()
{if(g[S.x][S.y] * || g[E.x][E.y] *) return false;memset(dist, -1, sizeof dist);dist[S.x][S.y] 0;queuePII q; q.push(S);while(q.size()){auto t q.front(); q.pop();if(t E) return dist[t.x][t.y]; // 防止起点即终点for(int i 0; i 8; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y m) continue;if(dist[x][y] ! -1 || g[x][y] *) continue; //*因为起始点都不是. ,如果 ! .访问不到终点dist[x][y] dist[t.x][t.y] 1;q.push({x,y}); }}return -1;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin m n; // 看清楚行列for(int i 0; i n; i) {cin g[i];for(int j 0; j m; j){if(g[i][j] K) S {i,j};if(g[i][j] H) E {i,j};}}cout bfs() endl;return 0;
}六、抓住那头牛
标签BFS
思路这道题实际上跟上一题差不多都是改变坐标只不过这种方式第一次可能写不出来但是看了一遍就会了其余的也只是正常写法。这里说一下为什么小于零或者大于两倍的 n n n 就非最优解因为答案存在于 0 ∼ n 0\sim n 0∼n 能走到零肯定是减到的所以之后唯一的操作就是加那就多余走了嘛。然后因为最多也只会走到这再走明显就不如之前了。
题目描述
农夫知道一头牛的位置想要抓住它。农夫和牛都位于数轴上农夫起始位于点 N牛位于点 K。农夫有两种移动方式从 X 移动到 X−1 或 X1每次移动花费一分钟从 X 移动到 2∗X每次移动花费一分钟假设牛没有意识到农夫的行动站在原地不动。农夫最少要花多少时间才能抓住牛输入格式
共一行包含两个整数N和K。输出格式
输出一个整数表示抓到牛所花费的最少时间。数据范围
0≤N,K≤105
输入样例
5 17
输出样例
4示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 2e510, M N, INF 0x3f3f3f3f;int n, m;
int dist[N];int bfs()
{memset(dist, -1, sizeof dist);dist[n] 0;queueint q; q.push(n);while(q.size()){int t q.front(); q.pop();if(t m) return dist[t];for(int i 0; i 3; i){int x;if(!i) x t - 1;else if(i 1) x t 1;else x t * 2;if(x 0 || x N) continue; // 因为已经非最优解了if(dist[x] ! -1) continue;dist[x] dist[t] 1;q.push(x); }}return -1;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;cout bfs() endl;return 0;
}七、矩阵距离
标签BFS、多源BFS
思路这道题问的是所有的格子到 1 1 1 的最短距离我们可以反过来从所有的 1 1 1 出发去求到所有的距离实际做法就是把所有的 1 1 1 入队并把距离初始化为 0 0 0 然后跑一遍 B F S BFS BFS 。
题目描述
给定一个 N 行 M 列的 01 矩阵 AA[i][j] 与 A[k][l] 之间的曼哈顿距离定义为dist(A[i][j],A[k][l])|i−k||j−l|输出一个 N 行 M 列的整数矩阵 B其中B[i][j]min1≤x≤N,1≤y≤M,A[x][y]1dist(A[i][j],A[x][y])输入格式
第一行两个整数 N,M。
接下来一个 N 行 M 列的 01 矩阵数字之间没有空格。输出格式
一个 N 行 M 列的矩阵 B相邻两个整数之间用一个空格隔开。数据范围
1≤N,M≤1000
输入样例
3 4
0001
0011
0110
输出样例
3 2 1 0
2 1 0 0
1 0 0 1示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010, M N, INF 0x3f3f3f3f;int n, m;
char g[N][N];
int dist[N][N];int dir[4][2] {0,1,0,-1,1,0,-1,0};void bfs()
{memset(dist, -1, sizeof dist);queuePII q;for(int i 0; i n; i){for(int j 0; j m; j){if(g[i][j] 1){dist[i][j] 0;q.push({i,j});}}}while(q.size()){auto t q.front(); q.pop();for(int i 0; i 4; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 0 || x n || y 0 || y m) continue;if(dist[x][y] ! -1) continue;dist[x][y] dist[t.x][t.y] 1;q.push({x,y});}}
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n m;for(int i 0; i n; i) cin g[i];bfs();for(int i 0; i n; i){for(int j 0; j m; j){cout dist[i][j] ;}cout endl;}return 0;
}八、魔板
标签BFS
思路其实就是状态的表示发生了变化我用的是如下图的一个对应的顺序其实这个表示方式不唯一只要输入输出和变化一一对应即可。我这里面的数字都是下标这样在变化的时候好理解。总的就是一个 B F S BFS BFS 然后每次取出队头进行三种变化由于字典序最小就按照 A B C ABC ABC 的顺序然后有一个哈希表存的是一对键值都是字符串分别对应当前的状态以及从起点到当前状态的操作方式具体就跟 d i s t dist dist 的作用是一样的还能用 c o u n t count count 方法来看这个状态是否访问过根据操作方法的顺序来增加操作方法然后就是具体的操作我就是根据具体的下标变化来赋值的。详情见代码发现结构跟抓住那头牛是一模一样只是状态和具体的操作不一样了而已。
题目描述
Rubik 先生在发明了风靡全球的魔方之后又发明了它的二维版本——魔板。这是一张有 8 个大小相同的格子的魔板1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。这 8 种颜色用前 8 个正整数来表示。可以用颜色的序列来表示一种魔板状态规定从魔板的左上角开始沿顺时针方向依次取出整数构成一个颜色序列。对于上图的魔板状态我们用序列 (1,2,3,4,5,6,7,8) 来表示这是基本状态。这里提供三种基本操作分别用大写字母 ABC 来表示可以通过这些操作改变魔板的状态A交换上下两行
B将最右边的一列插入到最左边
C魔板中央对的4个数作顺时针旋转。下面是对基本状态进行操作的示范A8 7 6 5
1 2 3 4
B4 1 2 3
5 8 7 6
C1 7 2 4
8 6 3 5
对于每种可能的状态这三种基本操作都可以使用。你要编程计算用最少的基本操作完成基本状态到特殊状态的转换输出基本操作序列。注意数据保证一定有解。输入格式
输入仅一行包括 8 个整数用空格分开表示目标状态。输出格式
输出文件的第一行包括一个整数表示最短操作序列的长度。如果操作序列的长度大于0则在第二行输出字典序最小的操作序列。数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。输入样例
2 6 8 4 5 7 3 1
输出样例
7
BCABCCB示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1e510, M N, INF 0x3f3f3f3f;int n, m;
unordered_mapstring,string dist;
string S 12345678, E;string dir ABC;string op1(string src)
{string res src;for(int i 0; i 4; i){swap(res[i], res[7-i]);}return res;
}string op2(string src)
{string res src;int t[8] {3,0,1,2,5,6,7,4};for(int i 0; i 8; i){res[i] src[t[i]];}return res;
}string op3(string src)
{string res src;res[1] src[6], res[2] src[1];res[5] src[2], res[6] src[5];return res;
}string bfs()
{dist[S] ;queuestring q; q.push(S);while(q.size()){auto t q.front(); q.pop();if(t E) return dist[E];for(int i 0; i 3; i){string x;if(!i) x op1(t);else if(i 1) x op2(t);else x op3(t);if(dist.count(x)) continue;dist[x] dist[t] dir[i];q.push(x); }}return impossible;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);string t; while(cin t) E t;string res bfs();cout res.size() endl;if(res.size()) cout res endl;return 0;
}
