当前位置： 首页 > article >正文

算法刷题day32

article 2025/1/20 2:00:18

目录

  • 引言
  • 一、走迷宫
  • 二、八数码
  • 三、走迷宫
  • 四、全球变暖

引言

本篇文章是讲 B F S BFS BFS 的，我发现好像蓝桥杯都很爱考陆地海洋的这种问题，这种问题就是即使你的模板背的再熟练，你想不到做法其实还是没啥用，所以多做题很重要，加油！

一、走迷宫

标签：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++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const 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;
	
	queue<PII> 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++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const int N = 1e5+10;

int n, m;
unordered_map<string,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*3+x.y;
}

int bfs()
{
	mmap[str] = 0;
	
	queue<string> 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++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
typedef pair<string,string> PSS;
#define x first
#define y second

const int N = 1e5+10;

int n, m;
unordered_map<string,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*3+x.y;
}

string bfs()
{
	mmap[str] = 0;
	
	queue<PSS> 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.y+dirr[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++.h>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;
#define x first
#define y second

const 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;
	queue<PII> 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;
}

http://www.kler.cn/a/272602.html

相关文章：

  • postgres数据库中_varchar的数组存储方法如何查找
  • STL—stack与queue
  • MySQL面试题2025 每日20道
  • springboot基于微信小程序的传统美食文化宣传平台小程序
  • SQLite 3.48.0 发布，有哪些更新？
  • 基于机器学习的用户健康风险分类及预测分析
  • mysql 索引（为什么选择B+ Tree?）
  • RocketMQ - 发送消息时Producer是如何选择MessageQueue去发送的？
  • 画图实战-Python实现某产品全年销量数据多种样式可视化
  • mac下Appuim环境安装
  • 【设计模式】Java 设计模式之工厂模式（Factory Pattern）
  • 就业班 2401--3.13 走进网络
  • Trustzone和Tee的基本概念区分
  • C语言文件操作 w模式
  • 【计算机网络篇】物理层（2）传输方式
  • 贪心算法（算法竞赛、蓝桥杯）--线段覆盖
  • #LLM入门|Prompt#3.3_存储_Memory
  • 生成器建造者模式（Builder）——创建型模式
  • QT 如何防止 QTextEdit 自动滚动到最下方
  • modbus客户端
  • Tensorflow笔记（二）：激活函数、优化器等、神经网络模型实现（商品销量预测）
  • C/C++程序设计实验报告3 | 数组实验
  • FPGA高端项目：FPGA基于GS2971+GS2972架构的SDI视频收发+HLS多路视频融合叠加，提供1套工程源码和技术支持
  • 配置LVS NAT模式
  • 单据分页的实现
  • 机试：高精度乘法