搜索最短路/最小步数问题

文章目录

  • 搜索专题之最短路/最小步数
    • 迷宫问题
      • 【题目描述】
      • 【输入样例】
      • 【输出样例】
      • 【AC代码】
    • 武士风度的牛
      • 【题目描述】
      • 【AC代码】
    • 抓住那头牛
      • 【题目描述】
      • 【AC代码】
    • 魔板
      • 【题目描述】
      • 【AC代码】

搜索专题之最短路/最小步数

迷宫问题

【题目描述】

在这里插入图片描述

【输入样例】

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

【AC代码】

#include <iostream>
#include <cstring>

#define x first 
#define y second
using namespace std;
const int N = 1010, M = N * N;
typedef pair<int, int> PII;
int g[N][N];
PII q[M];
PII pre[N][N];
int n;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int sx, int sy) {
	memset(pre, -1, sizeof pre);
	int hh = 0, tt = -1;
	q[++ tt] = {sx, sy};
	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 || 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;
}

武士风度的牛

【题目描述】

在这里插入图片描述
在这里插入图片描述

【AC代码】

#include <iostream>
#include <cstring>

#define x first
#define y second
using namespace std;
const int N = 160, M = N * N;
typedef pair<int, int> PII; 
char g[N][N];
int dist[N][N];
int m, n;
PII q[M];

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

int bfs(PII start, PII end) {
	int hh = 0, tt = -1;
	memset(dist, -1, sizeof dist);
	q[++ tt] = start;
	dist[start.x][start.y] = 0;
	
	while(hh <= tt) {
		PII 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;
			
			dist[a][b] = dist[t.x][t.y] + 1;
			q[++ tt] = {a, b};
			if(make_pair(a, b) == end)  return dist[a][b];
		}
	}
	return -1;
}

int main() {
	cin >> m >> n;
	for(int i = 0; i < n; i ++)	scanf("%s", &g[i]);
	PII start, end;
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < m; j ++) {
		
			if(g[i][j] == 'K')
				start = make_pair(i, j);
			if(g[i][j] == 'H')
				end = make_pair(i, j);
		}
	cout << bfs(start, end) << endl;
	return 0;
}

抓住那头牛

【题目描述】

在这里插入图片描述

【AC代码】

#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int dist[N];
int q[N];
int n, k;

int bfs() {
	memset(dist, -1, sizeof dist);
	int hh = 0, tt = -1;
	q[++ tt] = n;	//起点入队列
	dist[n] = 0;    //起点到起点为0
	
	while(hh <= tt) {
		int t = q[hh ++];
		if(t == k)	return dist[t];
		//三种走法遍历
		// x + 1
		if(t + 1 < N && dist[t + 1] == -1) {
			dist[t + 1] = dist[t] + 1;
			q[++ tt] = t + 1;
		} 
		//x - 1
		if(t - 1 >= 0 && dist[t - 1] == -1) {
			dist[t - 1] = dist[t] + 1;
			q[++ tt] = t - 1;
		}
		//x * 2
		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;
}

魔板

【题目描述】

在这里插入图片描述
在这里插入图片描述

【AC代码】

#include <cstring> // 引入cstring头文件,用于字符串操作
#include <iostream> // 引入iostream头文件,用于输入输出流操作
#include <algorithm> // 引入algorithm头文件,用于算法操作
#include <unordered_map> // 引入unordered_map头文件,用于哈希映射操作
#include <queue> // 引入queue头文件,用于队列操作

using namespace std;

char g[2][4]; // 定义一个二维字符数组g,表示状态
unordered_map<string, pair<char, string>> pre; // 定义一个哈希映射pre,存储状态的前驱和移动方式
unordered_map<string, int> dist; // 定义一个哈希映射dist,存储状态的最短距离

void set(string state)
{
    for (int i = 0; i < 4; i ++ ) g[0][i] = state[i]; // 将状态的前四个字符赋值给g的第一行
    for (int i = 7, j = 0; j < 4; i --, j ++ ) g[1][j] = state[i]; // 将状态的后四个字符赋值给g的第二行
}

string get()
{
    string res;
    for (int i = 0; i < 4; i ++ ) res += g[0][i]; // 将g的第一行字符拼接成字符串
    for (int i = 3; i >= 0; i -- ) res += g[1][i]; // 将g的第二行字符逆序拼接成字符串
    return res;
}

string move0(string state)
{
    set(state);
    for (int i = 0; i < 4; i ++ ) swap(g[0][i], g[1][i]); // 交换g的第一行和第二行的字符
    return get();
}

string move1(string state)
{
    set(state);
    int v0 = g[0][3], v1 = g[1][3]; // 保存g的第一行和第二行的最后一个字符
    for (int i = 3; i > 0; i -- )
    {
        g[0][i] = g[0][i - 1]; // 将g的第一行字符向右移动一位
        g[1][i] = g[1][i - 1]; // 将g的第二行字符向右移动一位
    }
    g[0][0] = v0, g[1][0] = v1; // 将保存的字符放到g的第一行和第二行的第一个位置
    return get();
}

string move2(string state)
{
    set(state);
    int v = g[0][1]; // 保存g的第一行的第二个字符
    g[0][1] = g[1][1]; // 将g的第二行的第二个字符赋值给g的第一行的第二个字符
    g[1][1] = g[1][2]; // 将g的第二行的第三个字符赋值给g的第二行的第二个字符
    g[1][2] = g[0][2]; // 将g的第一行的第三个字符赋值给g的第二行的第三个字符
    g[0][2] = v; // 将保存的字符放到g的第一行的第三个位置
    return get();
}

int bfs(string start, string end)
{
    if (start == end) return 0; // 如果起始状态和目标状态相同,返回0

    queue<string> q; // 定义一个队列q,用于广度优先搜索
    q.push(start); // 将起始状态加入队列
    dist[start] = 0; // 起始状态的最短距离为0

    while (!q.empty())
    {
        auto t = q.front(); // 取出队列的第一个元素
        q.pop(); // 弹出队列的第一个元素

        string m[3]; // 定义一个字符串数组m,存储移动后的状态
        m[0] = move0(t); // 将t进行move0操作得到移动后的状态m[0]
        m[1] = move1(t); // 将t进行move1操作得到移动后的状态m[1]
        m[2] = move2(t); // 将t进行move2操作得到移动后的状态m[2]

        for (int i = 0; i < 3; i ++ )
            if (!dist.count(m[i])) // 如果状态m[i]不在dist中
            {
                dist[m[i]] = dist[t] + 1; // 更新状态m[i]的最短距离
                pre[m[i]] = {'A' + i, t}; // 更新状态m[i]的前驱和移动方式
                q.push(m[i]); // 将状态m[i]加入队列
                if (m[i] == end) return dist[end]; // 如果状态m[i]等于目标状态,返回最短距离
            }
    }

    return -1; // 如果无法到达目标状态,返回-1
}

int main()
{
    int x;
    string start, end;
    for (int i = 0; i < 8; i ++ )
    {
        cin >> x; // 输入一个整数x
        end += char(x + '0'); // 将x转换为字符并添加到end字符串末尾
    }

    for (int i = 1; i <= 8; i ++ ) start += char('0' + i); // 初始化start字符串为"12345678"

    int step = bfs(start, end); // 进行广度优先搜索,得到最短步数

    cout << step << endl; // 输出最短步数

    // 有pre反推出变换序列
    string res;
    while (end != start)
    {
        res += pre[end].first; // 将当前状态的移动方式添加到res字符串末尾
        end = pre[end].second; // 更新当前状态为前驱状态
    }

    reverse(res.begin(), res.end()); // 将res字符串逆序

    if (step > 0) cout << res << endl; // 如果存在最短路径,输出移动方式

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515621.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Clang+LLVM+honggfuzz学习】(一)LLVM简介、安装和第一个Hello Pass

本文结构&#xff0c;PS:根据需要选择观看哦 1. 前言参考 2.简介传统编译器架构LLVM架构 3. LLVM安装版本准备官网源码下载git下载安装过程 4. 写一个LLVM Pass旧Hello Pass实现&#xff08;legacy PM version&#xff09;新Hello Pass实现&#xff08;Using the New Pass Mana…

GPT4不限制使用次数了!GPT5即将推出了!

今天登录到ChatGPT Plus账户&#xff0c;出现了如下提示&#xff1a; 已经没有了数量和时间限制的提示。 更改前&#xff1a;每 3 小时限制 40 次&#xff08;团队计划为 100 次&#xff09;&#xff1b;更改后&#xff1a;可能会应用使用限制。 GPT-4放开限制 身边订阅了Ch…

【C++STL详解 —— vector的介绍及使用】

【CSTL详解 —— vector的介绍及使用】 vector的介绍vector的使用vector的构造vector iterator 的使用begin和endrbegin和rend vector 空间增长问题size和capacityreserve和resizeempty vector 增删查改push_back和pop_backinsert和erasefindswap元素访问 vector 迭代器失效问题…

Vue 如何快速上手

目录 1. Vue 是什么 &#xff08;概念&#xff09; 1.1. Vue 的两种使用方式 1.2. 优点 1.3. 缺点 2. 创建 Vue 实例&#xff0c;初始化渲染 2.1. 步骤&#xff08;核心步骤 4步&#xff09; 2.2. 练习——创建一个Vue实例 3. 插值表达式 {{ }} 3.1. 介绍 3.2. 作用…

哈哈哈哈哈

欢迎使用Markdown编辑器 你好&#xff01; 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章&#xff0c;了解一下Markdown的基本语法知识。 222 我们对Markdown编辑器进行了一些功能拓展与语法支持&#xff0c;…

大创项目推荐 深度学习 python opencv 火焰检测识别

文章目录 0 前言1 基于YOLO的火焰检测与识别2 课题背景3 卷积神经网络3.1 卷积层3.2 池化层3.3 激活函数&#xff1a;3.4 全连接层3.5 使用tensorflow中keras模块实现卷积神经网络 4 YOLOV54.1 网络架构图4.2 输入端4.3 基准网络4.4 Neck网络4.5 Head输出层 5 数据集准备5.1 数…

文件管理--fscanf,fread,fwrite和fprintf

fprintf函数&#xff1a;对于fprintf函数&#xff0c;它和printf一样&#xff0c;但是它的表达式为&#xff1a;int fprintf ( FILE * stream, const char * format, ... );和printf的很相似&#xff0c;但有不一样。它是格式化输出函数&#xff0c;代码为&#xff1a; #includ…

模拟退火遗传算法GASA-附MATLAB代码

模拟退火遗传算法&#xff08;Simulated Annealing Genetic Algorithm&#xff0c;SAGA&#xff09;结合了模拟退火算法&#xff08;Simulated Annealing&#xff0c;SA&#xff09;和遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;的优点&#xff0c;用于解…

数字化导师坚鹏:招商银行数字化转型的4次模式升级与5大关键举措

招商银行数字化转型的4次模式升级与5大关键举措 招商银行数字化转型取得了较大的成功&#xff0c;从目前的财务数据来看&#xff0c;招商银行在数字化转型领域已经成为国内最优秀的股份制银行。招商银行是如何取得数字化转型成功的&#xff1f;从招商银行数字化转型的4次模式升…

先进电气技术 —— 控制理论之控制与扰动的战争

一、与扰动的斗争催生控制理论 在控制理论中&#xff0c;可以说“Identification&#xff08;辨识&#xff09;”、“Observe&#xff08;观测&#xff09;”、“Estimate&#xff08;估计&#xff09;”和“Control&#xff08;控制&#xff09;”这四个核心概念都是为了“消…

Centos7安装Docker与Docker-compose【图文教程】

个人记录 查看一下系统是否已经安装了Docker yum list installed | grep docker如下图代表没有安装Docker 卸载已有Docker yum remove docker docker-common docker-selinux docker-engine切换目录 cd /etc/yum.repos.d/查看当前目录所有的镜像源 ll安装yum-util与devi…

动态规划刷题(算法竞赛、蓝桥杯)--摆花(线性DP)

1、题目链接&#xff1a;[NOIP2012 普及组] 摆花 - 洛谷 #include <bits/stdc.h> using namespace std; const int mod1e67; const int N110; int n,m; int a[N],f[N][N]; //f[n][m]表示前n种花摆m盆的方案数 int main(){scanf("%d %d",&n,&m);for(in…

基于 Docker 的 python grpc quickstart

工作之后一直使用的 RPC 框架是 Apache 的 thrift&#xff0c;现在发现 grpc 更流行&#xff0c;所以也要学习一下&#xff0c;先来简单的跑一下 demo。在本地安装运行也很方便&#xff0c;不过因为有了 docker&#xff0c;所以在 docker 里面安装运行隔离性更好&#xff0c;顺…

并发线程基础第八篇

目录 线程池 自定义线程池 步骤1&#xff1a;自定义拒绝策略接口 步骤2&#xff1a;自定义任务队列 步骤3&#xff1a;自定义线程池 步 骤 4&#xff1a;测 试 ThreadPoolExecutor 线程池状态 构造方法 工作方式 newFixedThreadPool newCachedThreadPool newSingleTh…

算法day30 回溯6

332 重新安排行程 给你一份航线列表 tickets &#xff0c;其中 tickets[i] [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK&#xff08;肯尼迪国际机场&#xff09;出发的先生&#xff0c;所以该行程必须从 JFK …

【网站项目】果蔬经营平台系统

&#x1f64a;作者简介&#xff1a;拥有多年开发工作经验&#xff0c;分享技术代码帮助学生学习&#xff0c;独立完成自己的项目或者毕业设计。 代码可以私聊博主获取。&#x1f339;赠送计算机毕业设计600个选题excel文件&#xff0c;帮助大学选题。赠送开题报告模板&#xff…

红黑树的性质与操作:吸收红结点及其对树结构的影响

红黑树的性质与操作&#xff1a;吸收红结点及其对树结构的影响 1.红黑树的基本性质2.吸收红结点的过程2.1黑色结点的度2.2 叶结点深度 3.伪代码实现4. C语言代码实现5. 结论 红黑树作为一种高效的自平衡二叉搜索树&#xff0c;在计算机科学中扮演着重要的角色。它通过一系列复杂…

C++理解std::move和转发(std::forward)

理解 std::move 标准库move函数是使用右值引用的模板的一个很好的例子。 幸运的是&#xff0c;我们不必理解move所使用的模板机制也可以直接使用它。 但是&#xff0c;研究move是如何工作的可以帮助我们巩固对模板的理解和使用。 我们注意到&#xff0c;虽然不能直接将一个…

【C语言】linux内核pci_register_driver

一、注释 以下是对源代码中英文注释的中文翻译&#xff0c;可能会略去一些编程上的专有词汇&#xff08;例如函数名、类型名等&#xff09;&#xff0c;以使翻译更易理解。 // drivers\pci\pci-driver.c /*** __pci_register_driver - 注册一个新的PCI驱动* drv: 需要注册的驱…

【QT入门】 无边框窗口设计综合运用之自定义标题栏带圆角阴影的窗口

往期回顾&#xff1a; 【QT入门】 自定义标题栏界面qss美化按钮功能实现-CSDN博客 【QT入门】 无边框窗口设计之实现窗口阴影-CSDN博客 【QT入门】 无边框窗口设计之实现圆角窗口-CSDN博客 【QT入门】 无边框窗口设计综合运用之自定义标题栏带圆角阴影的窗口 一、最终效果 二、…