重庆市公路建设信息网官网,seo百度发包工具,图片制作视频的软件,网站开发 法律声明1.池塘计数
农夫约翰有一片 N ∗ M N∗M N∗M 的矩形土地。
最近#xff0c;由于降雨的原因#xff0c;部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内#xff0c;如果包含雨水#xff0c;则用”W”表示#xff0c;如果不含雨水#xff0c;…1.池塘计数
农夫约翰有一片 N ∗ M N∗M N∗M 的矩形土地。
最近由于降雨的原因部分土地被水淹没了。
现在用一个字符矩阵来表示他的土地。
每个单元格内如果包含雨水则用”W”表示如果不含雨水则用”.”表示。
现在约翰想知道他的土地中形成了多少片池塘。
每组相连的积水单元格集合可以看作是一片池塘。
每个单元格视为与其上、下、左、右、左上、右上、左下、右下八个邻近单元格相连。
请你输出共有多少片池塘即矩阵中共有多少片相连的”W”块。
输入格式 第一行包含两个整数 N N N 和 M M M。
接下来 N N N行每行包含 M M M个字符字符为”W”或”.”用以表示矩形土地的积水状况字符之间没有空格。
输出格式 输出一个整数表示池塘数目。
数据范围 1 ≤ N , M ≤ 1000 1≤N,M≤1000 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.输出样例
31.1题解 bfs
遍历单元格同时用一个标记数组记录标记每个单元格是否被访问过。
在遍历单元格过程中如果当前单元格是水并且没有被访问过水域数量1并且对该单元格进行bfs。
bfs 函数从当前单元格开始访问并标记和他同一片水域的单元格。
1.2代码实现
#includeiostream
#includealgorithm
#includecstring#define x first
#define y secondusing namespace std;//储存下标
typedef pairint,int PII;
const int N 1010,M N * N;int n,m;
char g[N][N];
PII q[M];
bool st[N][N]; //判重数组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];//取出队头//判断8连通一般使用双重循环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;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()
{scanf(%d%d,n,m);for(int i 0;i n;i) scanf(%s,g[i]);int cnt 0;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);cnt;}printf(%d,cnt);return 0;
}2.城堡问题 图1是一个城堡的地形图。
请你编写一个程序计算城堡一共有多少房间最大的房间有多大。
城堡被分割成 m ∗ n m∗n m∗n个方格区域每个方格区域可以有 0 4 0~4 0 4面墙。
注意墙体厚度忽略不计。
输入格式 第一行包含两个整数 m m m和 n n n分别表示城堡南北方向的长度和东西方向的长度。
接下来 m m m 行每行包含 n n n个整数每个整数都表示平面图对应位置的方块的墙的特征。
每个方块中墙的特征由数字 P P P来描述我们用 1 1 1表示西墙 2 2 2表示北墙 4 4 4表示东墙 8 8 8表示南墙 P P P为该方块包含墙的数字之和。
例如如果一个方块的 P P P为 3 3 3则 3 1 2 3 1 2 312该方块包含西墙和北墙。
城堡的内墙被计算两次方块 ( 1 , 1 ) (1,1) (1,1)的南墙同时也是方块 ( 2 , 1 ) (2,1) (2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出格式 共两行第一行输出房间总数第二行输出最大房间的面积方块数。
数据范围 1 ≤ m , n ≤ 50 , 1≤m,n≤50, 1≤m,n≤50, 0 ≤ P ≤ 15 0≤P≤15 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
92.1题解 不过本题中: 西墙表示:1,北墙表示:2,东墙表示:4,南墙表示:8 可以看出依次是 2 0 , 2 1 , 2 2 , 2 3 2^{0},2^{1},2^{2},2^{3} 20,21,22,23 所以可以用二进制来表示墙的分布情况. 例如: ( 0101 ) 2 (0101)_{2} (0101)2表示南,北边无墙,东,西边有墙
2.2代码实现
#includeiostream
#includealgorithm
#includecstring#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N 55,M N * N;int n,m;
int g[N][N];
PII q[M];
bool st[N][N];int bfs(int sx,int sy)
{//标记一下方向int dx[4] {0,-1,0,1},dy[4] {-1,0,1,0};int hh 0,tt 0;int area 0;q[0] {sx,sy};st[sx][sy] true;while(hh tt){PII t q[hh];area;//遍历四个方向for(int i 0; i 4;i){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)cin g[i][j];int cnt 0,area 0;for(int i 0;i n;i)for(int j 0;j m;j)if(!st[i][j]){area max(area,bfs(i,j));cnt;}cout cnt endl;cout area endl;return 0;
}3.山峰和山谷
FGD小朋友特别喜欢爬山在爬山的时候他就在研究山峰和山谷。
为了能够对旅程有一个安排他想知道山峰和山谷的数量。
给定一个地图为FGD想要旅行的区域地图被分为 n × n n×n n×n的网格每个格子 ( i , j ) (i,j) (i,j) 的高度 w ( i , j ) w(i,j) w(i,j)是给定的。
若两个格子有公共顶点那么它们就是相邻的格子如与 ( i , j ) (i,j) (i,j)相邻的格子有 ( i − 1 , j − 1 ) , ( i − 1 , j ) , ( i − 1 , j 1 ) , ( i , j − 1 ) , ( i , j 1 ) , ( i 1 , j − 1 ) , ( i 1 , j ) , ( i 1 , j 1 ) (i−1,j−1),(i−1,j),(i−1,j1),(i,j−1),(i,j1),(i1,j−1),(i1,j),(i1,j1) (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 S的所有格子都连通。对于 s s s属于 S S S与 s s s相邻的 s ′ s^{} s′不属于 S S S都有 w s w s ′ w_{s}w_{s^{}} wsws′山峰或者 w s w s ′ w_{s}w_{s^{}} wsws′山谷。如果周围不存在相邻区域则同时将其视为山峰和山谷。
你的任务是对于给定的地图求出山峰和山谷的数量如果所有格子都有相同的高度那么整个地图即是山峰又是山谷。
输入格式 第一行包含一个正整数 n n n表示地图的大小。
接下来一个 n × n n×n n×n 的矩阵表示地图上每个格子的高度 w w w。
输出格式 共一行包含两个整数表示山峰和山谷的数量。
数据范围 1 ≤ n ≤ 1000 , 1≤n≤1000, 1≤n≤1000, 0 ≤ w ≤ 1 0 9 0≤w≤10^{9} 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样例解释 样例1
样例2 3.1题解 3.2代码
#includecstring
#includeiostream
#includealgorithm#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N 1010,M N * N;int n;
int h[N][N];
PII q[M];
bool st[N][N];//引用在此传进去的参数是引用
void bfs(int sx,int sy,bool has_higher,bool has_lower)
{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;//把中间格子扣掉if(i 0 || i n || j 0 || j n) continue;if(h[i][j] ! h[t.x][t.y]) //山脉的边界{if(h[i][j] h[t.x][t.y]) has_higher true;else has_lower true;}else if(!st[i][j]){q[ tt] {i,j};st[i][j] true;}}}
}
int main()
{scanf(%d,n);for(int i 0;i n;i)for(int j 0;j n;j)scanf(%d,h[i][j]);int peak 0,valley 0;for(int i 0;i n;i)for(int j 0;j n;j)if(!st[i][j]){bool has_higher false,has_lower false;//使用传引用的方式bfs(i,j,has_higher,has_lower);if(!has_higher) peak;//注意在此不能单纯的使用else因为有可能即是山峰又是山谷if(!has_lower) valley;}printf(%d %d\n,peak,valley);return 0;
}
4.迷宫问题
给定一个 n × n n×n 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 1 1表示墙壁 0 0 0表示可以走的路只能横着走或竖着走不能斜着走要求编程序找出从左上角到右下角的最短路线。
数据保证至少存在一条从左上角走到右下角的路径。
输入格式 第一行包含整数 n n n。
接下来 n n n行每行包含 n n n个整数 0 0 0 或 1 1 1表示迷宫。
输出格式 输出从左上角到右下角的最短路线如果答案不唯一输出任意一条路径均可。
按顺序每行输出一个路径中经过的单元格的坐标左上角坐标为 ( 0 , 0 ) (0,0) (0,0)右下角坐标为 ( n − 1 , n − 1 ) (n−1,n−1) (n−1,n−1)。
数据范围 0 ≤ n ≤ 1000 0≤n≤1000 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 44.1题解
这道题是844题的扩展 我们这道题是想让我们将最短的路进行输出 我们的做法是用 p r e [ ] [ ] pre[][] pre[][]数组来记录当前结点前驱结点是哪个点以便我们输出它最短路径的坐标点 我们倒着寻找最短路径从 ( n − 1 , n − 1 ) (n-1,n-1) (n−1,n−1)开始 这样的话更新完 p r e pre pre数组 ( 0 , 0 ) (0,0) (0,0)就有它的前驱结点了 这样就能正着将 p r e pre pre数组中输出对应的路径了 关键和844的不同点就是如何维护 p r e pre pre这个记录路径的数组 以及你如何将这个数组数组也是有学问的
4.2代码
#includecstring
#includealgorithm
#includeiostream#define x first
#define y secondusing namespace std;typedef pairint,int PII;const int N 1010,M N * N;int n;
int g[N][N];
PII q[M];
PII pre[N][N]; //记录路径void bfs(int sx,int sy)
{//四个方向上右下左int dx[4] {-1,0,1,0},dy[4] {0,1,0,-1};int hh 0,tt 0;q[0] {sx,sy};memset(pre,-1,sizeof pre);pre[sx][sy] {0,0};while(hh tt){PII t q[hh ];for(int i 0;i 4;i){int a t.x dx[i],b t.y dy[i];if(a 0 || a n || b 0 || b n) continue;if(g[a][b]) continue;if(pre[a][b].x ! -1) continue;q[ tt] {a,b};pre[a][b] t;}}
}
int main()
{scanf(%d,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;end pre[end.x][end.y];}return 0;}
5.武士风度的牛
农民 J o h n John John 有很多牛他想交易其中一头被 D o n Don Don 称为 T h e K n i g h t The Knight TheKnight 的牛。
这头牛有一个独一无二的超能力在农场里像 K n i g h t Knight Knight 一样地跳就是我们熟悉的象棋中马的走法。
虽然这头神奇的牛不能跳到树上和石头上但是它可以在牧场上随意跳我们把牧场用一个 x y xy xy的坐标图来表示。
这头神奇的牛像其它牛一样喜欢吃草给你一张地图上面标注了 T h e K n i g h t The Knight TheKnight 的开始位置树、灌木、石头以及其它障碍的位置除此之外还有一捆草。
现在你的任务是确定 T h e K n i g h t The Knight TheKnight 要想吃到草至少需要跳多少次。 T h e K n i g h t The Knight TheKnight 的位置用 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 T h e K n i g h t The Knight TheKnight 可以按照下图中的 A , B , C , D … A,B,C,D… A,B,C,D…这条路径用 5 5 5次跳到草的地方有可能其它路线的长度也是 5 5 5: 11 | . . . . . . . . . .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 1 1 行 两个数表示农场的列数 C C C 和行数 R R R。
第 2.. R 1 2..R1 2..R1行: 每行一个由 C C C 个字符组成的字符串共同描绘出牧场地图。
输出格式 一个整数表示跳跃的最小次数。
数据范围 1 ≤ R , C ≤ 150 1≤R,C≤150 1≤R,C≤150 输入样例
10 11
..........
....*.....
..........
...*.*....
.......*..
..*..*...H
*.........
...*...*..
.K........
...*.....*
..*....*..输出样例
55.1题解
广度优先搜索 一般来说走迷宫,最少步数这种题目,都是广度优先搜索.记住读入上面的有梗,然后修改一下一般走路方式就好了.
5.2代码实现
#includecstring
#includeiostream
#includealgorithm#define x first
#define y secondusing namespace std;typedef pairint,int PII;
const int N 155,M N * N;int n,m;
char g[N][N];
PII q[M];
int dist[N][N];//存储最短路int bfs()
{int dx[8] {-2,-1,1,2,2,1,-1,-2};int dy[8] {1,2,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;int hh 0,tt 0;q[0] {sx,sy};memset(dist,-1,sizeof dist);dist[sx][sy] 0;while(hh tt){auto t q[hh ];for(int i 0;i 8;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};}}return -1;
}
int main()
{cin m n;for(int i 0;i n;i) cin g [i];cout bfs() endl;return 0;}6.抓住那头牛
农夫知道一头牛的位置想要抓住它。
农夫和牛都位于数轴上农夫起始位于点 N N N牛位于点 K K K。
农夫有两种移动方式
从 X X X移动到 X − 1 X−1 X−1或 X 1 X1 X1每次移动花费一分钟从 X X X 移动到 2 ∗ X 2∗X 2∗X每次移动花费一分钟
假设牛没有意识到农夫的行动站在原地不动。
农夫最少要花多少时间才能抓住牛
输入格式 共一行包含两个整数 N N N和 K K K。
输出格式 输出一个整数表示抓到牛所花费的最少时间。
数据范围 0 ≤ N , K ≤ 1 0 5 0≤N,K≤10^{5} 0≤N,K≤105 输入样例
5 17输出样例
45.1题解
看完题目以后农夫不就是向右移动{-1,1当前位置}这三种情况吗 于是就普通至极至于范围的话 如果 k 1 e 5 , n 50000 k1e^{5},n50000 k1e5,n50000时实际上最短步数一定只有两种情况
如果 n − 50000 k − n n-50000k-n n−50000k−n时就会后退到 50000 50000 50000再 ∗ 2 *2 ∗2否则就一直 1 1 1到 k k k
范围就是 0 n 1 e 5 0n1e^{5} 0n1e5
5.2代码
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 1e5 10;int n, k;
int q[N];
int dist[N];int bfs()
{memset(dist, -1, sizeof dist);dist[n] 0;q[0] n;int hh 0, tt 0;while (hh tt){int t q[hh ];if (t k) return dist[k];if (t 1 N dist[t 1] -1){dist[t 1] dist[t] 1;q[ tt] t 1;}if (t - 1 0 dist[t - 1] -1){dist[t - 1] dist[t] 1;q[ tt] t - 1;}if (t * 2 N dist[t * 2] -1){dist[t * 2] dist[t] 1;q[ tt] t * 2;}}return -1;
}int main()
{cin n k;cout bfs() endl;return 0;
}
