D3-八数码

D3-八数码

  • 题目描述
  • 解题思路
  • 代码如下

题目描述

在这里插入图片描述

解题思路

本题若直接在3*3网格中思考较为困难,可以转换为一维的字符串,在一维字符串中考虑较为简单,要注意本题中两个字符交换位置时只能是x和另外字符交换,本题另外一个难点在于如何维护一个距离数组用于表示交换的次数(可用map,代码中会有注释)

代码如下

#include<bits/stdc++.h>
using namespace std;
unordered_map<string,int> dist;//维护一个从开始状态到结束状态的转换次数
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//上下左右移动的数轴,dx是左右移动,dy是上下移动
string s1="12345678x";//最终状态,用于和中间状态进行比较

int bfs(string s)
{
  queue<string> q;
  q.push(s);
  dist[s]=0;//刚开始是转换次数为0
  while(q.size())
  {
    string f=q.front();
    q.pop();
    int distance = dist[f];//将这个状态的转换次数存起来,因为下面会交换元素位置
    if(f==s1) return distance;
    int k=f.find('x');
    int x=k/3,y=k%3;//将s中的元素的一维位置转换为3*3的位置元素
    for(int i=0;i<4;i++)
    {
      int a=x+dx[i],b=y+dy[i];
      if(a>=0&&a<3&&b>=0&&b<3)
      {
        swap(f[k],f[a*3+b]);//再将3*3中的位置转换为s中的一维位置
        if(!dist.count(f))
        {
          dist[f] = distance+1;
          q.push(f);
        }
        swap(f[k],f[a*3+b]);//转换完之后要再转回来
      }
    }
  }
  return -1;
}

int main()
{
  string s;
  char c;
  for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    {
      cin>>c;
      s+=c;
    }
  cout<<bfs(s)<<endl;
  return 0;
}

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

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

相关文章

TypeScript系列之-深度理解基本类型画图讲解

JS的类型(8)&#xff1a; null undefined string number boolean bigint symbol object&#xff08;含 Array, Function,Date.....&#xff09; TS的类型(87): 以上所有&#xff0c;加上 void, never, enum, unknown, any 再加上自定义类型 type interface 上一节我们说…

判断IQ水平-第12届蓝桥杯选拔赛Python真题精选

[导读]&#xff1a;超平老师的Scratch蓝桥杯真题解读系列在推出之后&#xff0c;受到了广大老师和家长的好评&#xff0c;非常感谢各位的认可和厚爱。作为回馈&#xff0c;超平老师计划推出《Python蓝桥杯真题解析100讲》&#xff0c;这是解读系列的第50讲。 判断IQ水平&#…

利用栈删除数组中重复元素

先将数据排序&#xff08;降序或升序&#xff09; 建立一个“栈”&#xff0c;三种情况&#xff1a; 1.栈为空&#xff1a;压入一个元素 2.栈不为空 且 栈顶元素不等于将入栈元素&#xff1a;压入一个元素 3.栈不为空 且 栈顶元素等于将入栈元素&#xff1a;删除将压入元素…

SCI 四区(JEI)投稿到录用过程中的经历和心得体会

计算机视觉领域中&#xff0c;包含目标检测、三维重建、语义分割、图像分类等分支。其中&#xff0c;目标检测分支最卷&#xff0c;你知道的&#xff0c;没有背景和资源&#xff0c;发一篇SCI属实不易。本篇博客详细介绍本人投稿到录用过程中的经历和心得。 目录 1. 硬件资源落…

微信云开发小程序的服务器是属于服务商的还是商家的

越来越多的小程序&#xff0c;选择使用微信云开发来进行开发。然而&#xff0c;关于微信云开发小程序的服务器归属权问题&#xff0c;往往会引起一些商家的疑虑。本文将详细解析微信云开发小程序的服务器是属于服务商的还是商家的。 首先&#xff0c;我们需要明确微信云开发的概…

maven引入外部jar包

将jar包放入文件夹lib包中 pom文件 <dependency><groupId>com.jyx</groupId><artifactId>Spring-xxl</artifactId><version>1.0-SNAPSHOT</version><scope>system</scope><systemPath>${project.basedir}/lib/Spr…

1042: 中缀表达式转换为后缀表达式

解法&#xff1a;直接给算法 创建一个栈和一个空的后缀表达式字符串。 遍历中缀表达式中的每个字符。 如果当前字符是操作数&#xff0c;直接将其添加到后缀表达式字符串中。 如果当前字符是操作符&#xff0c;需要将其与栈顶的操作符进行比较&#xff1a; 如果栈为空&#…

动态规划专练( 337.组合总和Ⅳ)

337.组合总和Ⅳ 给你一个由 不同 整数组成的数组 nums &#xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。 题目数据保证答案符合 32 位整数范围。 示例 1&#xff1a; 输入&#xff1a;nums [1,2,3], target 4 输出&#x…

2022年蓝桥杯省赛软件类C/C++B组----积木画

想借着这一个题回顾一下动态规划问题的基本解法&#xff0c;让解题方法清晰有条理&#xff0c;希望更多的人可以更轻松的理解动态规划&#xff01; 目录 【题目】 【本题解题思路】 【DP模版】 总体方针&#xff1a; 具体解题时的套路&#xff1a; 【题目】 【本题解题思…

Python判断节假日的几种方式,你学废了吗?

最近在推进信息安全巡检的工作&#xff0c;按公司制度要求和信息安全标准&#xff0c;要求按时对硬件设备、网络、机房、应用系统、数据库等等做巡检工作。为了保证达到信息安全的目标&#xff0c;要求在每周四和节假日的前一天对各类设备和系统进行巡检。 1、使用holidays库判…

zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

一、zookeeper基本介绍 1.1 zookeeper的概念 Zookeeper是一个开源的分布式的&#xff0c;为分布式框架提供协调服务的Apache项目。 是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件&#xff0c;提供的功能包括&#xff1a;配置维护、域名服务、…

python小游戏

这些游戏你玩过几个&#xff1f; 1.贪吃蛇2.吃豆人3.加农炮4.四子棋5. Fly Bird<font color #f3704ab>6.记忆&#xff1a;数字对拼图游戏&#xff08;欢迎挑战&#xff01;用时&#xff1a;2min&#xff09;7.乒乓球8.上课划水必备-井字游戏&#xff08;我敢说100%的人都…

代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和 思路&#xff1a; 本题和77.组合 &#xff0c;216.组合总和III的区别是&#xff1a;本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本题搜索的过程抽象成树形结构如下&#xff1a; 注意图中叶…

《HF经理》:二认知误区

一、管理者掌握重要权力&#xff1a; 二、全力来自管理者的职位&#xff1a; 三、管理者必须控制自己的直接下属&#xff1a; 对策&#xff1a;展示自己的品质&#xff0c;能力和影响力 四、管理者必须建立良好的个人关系&#xff1a; 五、管理这必须确保一切运行正常&…

【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】

爬虫开发从0到1全知识教程完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;爬虫课程概要&#xff0c;爬虫基础爬虫概述,,http协议复习。requests模块&#xff0c;requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…

分享2024 golang学习路线

写在前面 Go语言&#xff08;也称为Golang&#xff09;是Google开发的一种静态强类型、编译型语言&#xff0c;它具有简洁、快速、安全、并发等特点&#xff0c;尤其适合构建大型软件、微服务架构和云平台服务。Go的学习曲线相对平缓&#xff0c;社区活跃&#xff0c;是现代编…

韩顺平 | 零基础快速学Python(16) 文件处理

文件 输入与输出 输入&#xff1a;数据从数据源(文件)到程序(内存)&#xff1b; 输出&#xff1a;数据从程序(内存)到数据源(文件)。 #mermaid-svg-06PG6JZq4jJMV1oH {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-sv…

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说&#xff0c;Ribbon是Netflix发布的开源项目&#xff0c;主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…

掌握CRM+邮箱技巧:销售速度与客户信任双丰收

在千行百业都在谈提效的今天&#xff0c;如果您的销售团队效率较低&#xff0c;恐怕很难过好2024。销售团队提效是个大话题&#xff0c;总的说来就是销售团队需要在正确的时间做正确的事。如何做到&#xff1f;自然要借助CRM工具。过去我们也讲了不少CRM如何辅助销售团队提效的…

Playwright已经是目前最好的测试自动化工具了吗?

作者观点&#xff1a;很长时间以来&#xff0c;Selenium是QA工程师寻求测试自动化解决方案的首选测试框架。它能够测试任何浏览器&#xff08;这在IE浏览器的统治时期尤其重要&#xff09;和任何平台。然而&#xff0c;现在看来&#xff0c;那个时代已经过去了。 今天&#xf…