潍坊 区网站建设,做毕业设计网站教程,志愿北京网站注册,免费观看电影电视剧的app下载目录 引言一、走迷宫二、八数码三、走迷宫四、全球变暖 引言
本篇文章是讲 B F S BFS BFS 的#xff0c;我发现好像蓝桥杯都很爱考陆地海洋的这种问题#xff0c;这种问题就是即使你的模板背的再熟练#xff0c;你想不到做法其实还是没啥用#xff0c;所以多做题很重要我发现好像蓝桥杯都很爱考陆地海洋的这种问题这种问题就是即使你的模板背的再熟练你想不到做法其实还是没啥用所以多做题很重要加油 一、走迷宫
标签BFS
思路模板题没啥说的这种题有些注意的地方 1. 1. 1. 起点和终点可能是一个点。 2. 2. 2. 起点或者终点有可能就走不了。
题目描述
给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。最初有一个人位于左上角 (1,1) 处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问该人从左上角移动至右下角 (n,m) 处至少需要移动多少次。数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。输入格式
第一行包含两个整数 n 和 m。接下来 n 行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。输出格式
输出一个整数表示从左上角移动至右下角的最少移动次数。数据范围
1≤n,m≤100
输入样例
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
输出样例
8示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 110;int n, m;
int g[N][N];
int dist[N][N];int dir[4][2] {0,1,0,-1,1,0,-1,0};int bfs()
{memset(dist, -1, sizeof dist);dist[1][1] 0;queuePII q; q.push({1,1});while(q.size()){auto t q.front(); q.pop();if(t.x n t.y m) return dist[n][m];for(int i 0; i 4; i){int x t.x dir[i][0];int y t.y dir[i][1];if(x 1 || x n || y 1 || y m) continue;if(dist[x][y] ! -1 || g[x][y] 1) 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 n m;for(int i 1; i n; i){for(int j 1; j m; j){cin g[i][j];}}cout bfs() endl;return 0;
}二、八数码
标签BFS
思路核心还是 B F S BFS BFS 把这种顺序抽象成一个字符串来存然后通过映射来找到 x x x 的横纵坐标再对其上下左右移动判断是否合法用 m a p map map 来统计是否出现和交换的次数再进行交换入队。
题目描述
在一个 3×3 的网格中1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。例如1 2 3
x 4 6
7 5 8
在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。我们的目的是通过交换使得网格变为如下排列称为正确排列1 2 3
4 5 6
7 8 x
例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
现在给你一个初始网格请你求出得到正确排列至少需要进行多少次交换。输入格式
输入占一行将 3×3 的初始网格描绘出来。例如如果初始网格如下所示1 2 3
x 4 6
7 5 8
则输入为1 2 3 x 4 6 7 5 8输出格式
输出占一行包含一个整数表示最少交换次数。如果不存在解决方案则输出 −1。输入样例
2 3 4 1 5 x 7 6 8
输出样例
19示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1e510;int n, m;
unordered_mapstring,int mmap;
string str, E 12345678x;int dir[4][2] {0,1,0,-1,1,0,-1,0};PII get1(int x)
{return {x/3,x%3};
}int get2(PII x)
{return x.x*3x.y;
}int bfs()
{mmap[str] 0;queuestring q; q.push(str);while(q.size()){auto t q.front(); q.pop();if(t E) return mmap[E];int k t.find(x);PII t1 get1(k); PII t2 t1;for(int i 0; i 4; i){int x t1.x dir[i][0];int y t1.y dir[i][1];if(x 0 || x 3 || y 0 || y 3) continue;int k2 get2({x,y});string tmp t;swap(tmp[k],tmp[k2]);if(mmap.count(tmp)) continue;mmap[tmp] mmap[t] 1;q.push(tmp);}}return -1;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);for(int i 0; i 9; i){char t; cin t;str t;}cout bfs() endl;return 0;
}三、走迷宫
标签BFS
思路其实核心跟上一题一样的只不过要输出交换的方案我们可以把入队的元素再加一个字符串用来表示最终的答案根据 d i r dir dir 的移动顺序对应一个字符串的移动方案然后其它的就跟上一题是一样的了。
题目描述
在一个 3×3 的网格中1∼8 这 8 个数字和一个 x 恰好不重不漏地分布在这 3×3 的网格中。例如1 2 3
x 4 6
7 5 8
在游戏过程中可以把 x 与其上、下、左、右四个方向之一的数字交换如果存在。我们的目的是通过交换使得网格变为如下排列称为正确排列1 2 3
4 5 6
7 8 x
例如示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。交换过程如下1 2 3 1 2 3 1 2 3 1 2 3
x 4 6 4 x 6 4 5 6 4 5 6
7 5 8 7 5 8 7 x 8 7 8 x
把 x 与上下左右方向数字交换的行动记录为 u、d、l、r。现在给你一个初始网格请你通过最少的移动次数得到正确排列。输入格式
输入占一行将 3×3 的初始网格描绘出来。例如如果初始网格如下所示1 2 3
x 4 6
7 5 8
则输入为1 2 3 x 4 6 7 5 8输出格式
输出占一行包含一个字符串表示得到正确排列的完整行动记录。如果答案不唯一输出任意一种合法方案即可。如果不存在解决方案则输出 unsolvable。输入样例
2 3 4 1 5 x 7 6 8
输出样例
ullddrurdllurdruldr示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
typedef pairstring,string PSS;
#define x first
#define y secondconst int N 1e510;int n, m;
unordered_mapstring,int mmap;
string str, E 12345678x;int dir[4][2] {0,1,0,-1,1,0,-1,0};
string dirr[4] {r,l,d,u};PII get1(int x)
{return {x/3,x%3};
}int get2(PII x)
{return x.x*3x.y;
}string bfs()
{mmap[str] 0;queuePSS q; q.push({str,});while(q.size()){auto t q.front(); q.pop();if(t.x E) return t.y;int k t.x.find(x);PII t1 get1(k); PII t2 t1;for(int i 0; i 4; i){int x t1.x dir[i][0];int y t1.y dir[i][1];if(x 0 || x 3 || y 0 || y 3) continue;int k2 get2({x,y});string tmp t.x;swap(tmp[k],tmp[k2]);if(mmap.count(tmp)) continue;mmap[tmp] mmap[t.x] 1;q.push({tmp,t.ydirr[i]});}}return unsolvable;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);for(int i 0; i 9; i){char t; cin t;str t;}cout bfs() endl;return 0;
}四、全球变暖
标签BFS
思路在遍历每一块陆地的时候统计该块陆地的陆地数和之后的海洋数陆地数就是入对的个数海洋数就是每块陆地是否有一边挨着海洋然后看是否陆地数等于海洋数等于最终答案加一。
题目描述
你有一张某海域 N×N 像素的照片”.”表示海洋、”#”表示陆地如下所示.......
.##....
.##....
....##.
..####.
...###.
.......
其中”上下左右”四个方向上连在一起的一片陆地组成一座岛屿例如上图就有 2 座岛屿。由于全球变暖导致了海面上升科学家预测未来几十年岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)它就会被淹没。例如上图中的海域未来会变成如下样子.......
.......
.......
.......
....#..
.......
.......
请你计算依照科学家的预测照片中有多少岛屿会被完全淹没。输入格式
第一行包含一个整数N。以下 N 行 N 列包含一个由字符”#”和”.”构成的 N×N 字符矩阵代表一张海域照片”#”表示陆地”.”表示海洋。照片保证第 1 行、第 1 列、第 N 行、第 N 列的像素都是海洋。输出格式
一个整数表示答案。数据范围
1≤N≤1000
输入样例1
7
.......
.##....
.##....
....##.
..####.
...###.
.......
输出样例1
1
输入样例2
9
.........
.##.##...
.#####...
.##.##...
.........
.##.#....
.#.###...
.#..#....
.........
输出样例2
1示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;
#define x first
#define y secondconst int N 1010;int n, m;
char g[N][N];
bool st[N][N];int dir[4][2] {0,1,0,-1,1,0,-1,0};bool bfs(PII S)
{st[S.x][S.y] true;int sea 0, oil 1;queuePII q; q.push({S.x,S.y});while(q.size()){auto t q.front(); q.pop();bool flag false;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]) continue;if(g[x][y] .) {flag true; continue;}oil;st[x][y] true;q.push({x,y});}if(flag) sea;}return sea oil;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin n;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 n; j){if(!st[i][j] g[i][j] #){if(bfs({i,j})) res;}}}cout res endl;return 0;
}
