图论08-图的建模-状态的表达与理解 - 倒水问题为例

文章目录

  • 状态的表达
    • 例题1
    • 题解
      • 1 终止条件:有一个数位为4
      • 2 状态的改变:a表示十位数,b表示个位数
      • 3 其他设置
    • 例题2 力扣773 滑动谜题
      • Java
      • C++

状态的表达

例题1

在这里插入图片描述

从初始的(x,y)状态,到最后变成(4,?)或者(?,4).

本道题对于(x,y)的状态,可以使用10x+y进行表达,也就是变成了一个数字,分别放在不同的数位上。
但是本状态的表示方法不适用单个数组超过9的,因为一个数位只能表示0-9.。

涉及思想:状态压缩

题解

1 终止条件:有一个数位为4

if(next / 10 == 4 || next % 10 == 4) {end = next;return;
}

2 状态的改变:a表示十位数,b表示个位数

重复添加满水不影响结果

a = cur / 10, b = cur % 10;

要达到(4,?)或者(?,4)的办法

  • a桶灌满5升水
  • b桶灌满3升水
  • a桶的水倒掉
  • b桶的水倒掉
  • a桶中的水倒进b桶中 --> 最多能倒a升,还能倒b桶剩余空闲容量=(3-b桶当前容量)
  • b桶中的水倒进a桶中
nexts.add(5 * 10 + b);
nexts.add(a * 10 + 3);
nexts.add(a * 10 + 0);
nexts.add(0 * 10 + b);int x = Math.min(a, 3 - b);
nexts.add((a - x) * 10 + (b + x));int y = Math.min(b, 5 - a);
nexts.add((a + y) * 10 + (b - y));

3 其他设置

  • 访问数组用于记录访问过的状态
 boolean[] visited = new boolean[100];
  • 队列用于记录访问的每个节点的状态
Queue<Integer> queue = new LinkedList<>();
  • 记录上一个状态
pre = new int[100];
  • 记录状态变化
    • 首先要把pre数组填好,根据pre数组将遍历的过程从最终结果向前找初始状态。最终再翻转链表。
    • 做标记 设置end = -1
      如果end倒最后还是-1,说明问题没有解。
import java.util.*;
import java.util.ArrayList;public class WaterPuzzle {private int[] pre;private int end = -1;public WaterPuzzle(){Queue<Integer> queue = new LinkedList<>();boolean[] visited = new boolean[100];pre = new int[100];queue.add(0);visited[0] = true;while (!queue.isEmpty()){int cur = queue.remove();int a = cur / 10, b = cur % 10;// max a = 5, max b = 3ArrayList<Integer> nexts = new ArrayList<>();nexts.add(5 * 10 + b);nexts.add(a * 10 + 3);nexts.add(a * 10 + 0);nexts.add(0 * 10 + b);int x = Math.min(a, 3 - b);nexts.add((a - x) * 10 + (b + x));int y = Math.min(b, 5 - a);nexts.add((a + y) * 10 + (b - y));for(int next: nexts)if(!visited[next]){queue.add(next);visited[next] = true;pre[next] = cur;if(next / 10 == 4 || next % 10 == 4) {end = next;return;}}}}public Iterable<Integer> result(){ArrayList<Integer> res = new ArrayList<>();if(end == -1) return res;int cur = end;while(cur != 0){res.add(cur);cur = pre[cur];}res.add(0);Collections.reverse(res);return res;}public static void main(String[] args){System.out.println((new WaterPuzzle()).result());}
}

例题2 力扣773 滑动谜题

Java

/// Leetcode 773import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.HashMap;public class Solution {private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};public int slidingPuzzle(int[][] board) {Queue<String> queue = new LinkedList<>();HashMap<String, Integer> visited = new HashMap<>();String initalState = boardToString(board);if(initalState.equals("123450")) return 0;queue.add(initalState);visited.put(initalState, 0);while(!queue.isEmpty()){String cur = queue.remove();ArrayList<String> nexts = getNexts(cur);for(String next: nexts)if(!visited.containsKey(next)){queue.add(next);visited.put(next, visited.get(cur) + 1);if(next.equals("123450"))return visited.get(next);}}return -1;}private ArrayList<String> getNexts(String s){int[][] cur = stringToBoard(s);int zero;for(zero = 0; zero < 6; zero ++)if(cur[zero / 3][zero % 3] == 0)break;ArrayList<String> res = new ArrayList<>();int zx = zero / 3, zy = zero % 3;for(int d = 0; d < 4; d ++){int nextx = zx + dirs[d][0], nexty = zy + dirs[d][1];if(inArea(nextx, nexty)){swap(cur, zx, zy, nextx, nexty);res.add(boardToString(cur));swap(cur, zx, zy, nextx, nexty);}}return res;}private boolean inArea(int x, int y){return x >= 0 && x < 2 && y >= 0 && y < 3;}private void swap(int[][] board, int x1, int y1, int x2, int y2){int t = board[x1][y1];board[x1][y1] = board[x2][y2];board[x2][y2] = t;}private String boardToString(int[][] board){StringBuilder sb = new StringBuilder();for(int i = 0; i < 2; i ++)for(int j = 0; j < 3; j ++)sb.append(board[i][j]);return sb.toString();}private int[][] stringToBoard(String s){int[][] board = new int[2][3];for(int i = 0; i < 6; i ++)board[i / 3][i % 3] = s.charAt(i) - '0';return board;}public static void main(String[] args){int[][] board = {{1, 2, 3}, {4, 0, 5}};System.out.println((new Solution()).slidingPuzzle(board));}
}

C++

class Solution {
public:int slidingPuzzle(vector<vector<int>>& board) {
//记录最终状态const string sol = "123450";const int m = 2, n = 3;const int dirs[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//记录初始状态,使用字符串记录string init;for (auto &line: board) {for (auto &grid: line) {init.push_back('0' + grid);}}//构造队列,并初始化queue<string> q{{init}};//设置unordered_set,记录访问状态unordered_set<string> vis{{init}};//记录步数int ans = 0;//开始BFSwhile (!q.empty()) {int size = q.size();for (int i = 0; i < size; ++i) {auto &p = q.front();//出口if (p == sol) {return ans;}//先找0号的位置int idx0 = p.find('0');//四联通拓展for (int a = 0; a < 4; ++a) {//求0号元素的二维新坐标int nx = idx0 / n + dirs[a][0], ny = idx0 % n + dirs[a][1];//求0号元素映射到一维数组中的坐标int idx1 = nx * n + ny;//判断边界if (nx >= 0 && nx < m && ny >= 0 && ny < n) {//交换两个元素的位置swap(p[idx0], p[idx1]);//如果当前状态没有测试过if (!vis.count(p)) {//加入访问数组vis.insert(p);//入队q.push(p);}//恢复原来的状态,继续交换位置然后将状态入队列swap(p[idx0], p[idx1]);}}q.pop();}//对头出队的时候,开始移动到下一个状态,因此步数+1++ans;}return -1;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SOLIDWORKS 2024新功能--SOLIDWORKS Electrical篇

SOLIDWORKS Electrical 对齐零部件 在设计 3D 机柜布局时使用对齐零部件时&#xff0c;可以在图形区域中预览更改。这大大减少了在 3D 机柜布局中对齐 SOLIDWORKS 零部件所需的工作量。对齐零部件 PropertyManager 简化并改进了工作流程。 SOLIDWORKS Electrical 更改多个导…

跨境电商须知| 独立站的特点与痛点有哪些?

独立站的特点与痛点有哪些&#xff1f; 无论是做独立站&#xff0c;还是做亚马逊&#xff0c;都有各自的难点。自己做独立站若要在跨境行业长足发展&#xff0c;既要知道独立站有什么特点&#xff0c;要清楚独立站的痛点并一一克服。了解独立站搭建更多 一、独立站的特点 1、…

全球最杰出的大神程序员们(14位)

一、全球杰出的程序员介绍 一起来认识一下全球最杰出的大神程序员们。可惜没看到国人的面孔&#xff01;&#xff08;排名不分先后&#xff09; 1、Jon Skeet 个人名望&#xff1a;程序技术问答网站 Stack Overflow 总排名第一的大神&#xff0c;每月的问答量保持在 425 个左…

uniapp 编译到模拟器(mumu)

一开始我是用逍遥模拟器&#xff0c;但这个玩意突然不好使了&#xff0c;一直加载卡在这页面 1、下载 官网下载&#xff1a;mumu模拟器12 2、打开mumu多开器&#xff0c;在右上角adb查看端口号 3、打开mumu模拟器 4、打开HBuiderX 工具—设置—运行配置 5、配置电脑的系统…

Selenium安装WebDriver Chrome驱动(含 116/117/118/119/120/)

1、确认浏览器的版本 在浏览器的地址栏&#xff0c;输入chrome://version/&#xff0c;回车后即可查看到对应版本 2、找到对应的chromedriver版本 2.1 114及之前的版本可以通过点击下载chromedriver,根据版本号&#xff08;只看大版本&#xff09;下载对应文件 2.2 116版本…

【前端笔记】ant-design-vue 3.x使用modal.method()自定义content内容小记

在一次编写业务代码时&#xff0c;碰到了一种既想要Modal.success样式&#xff0c;有想要定制其content内容的情况。 大部分情况下&#xff0c;使用Modal.method()这种方式时&#xff0c;可能content内容固定都是字符串&#xff0c;那如果想要做更高级的交互怎么办&#xff1f…

回溯算法(2)--图着色问题和旅行商问题

目录 一、图着色问题 1、算法设计 2、代码 二、旅行商问题 1、概述问题 2、穷举法 3、回溯法 一、图着色问题 1、算法设计 图着色问题&#xff0c;给定图中各个区域的相邻关系&#xff0c;抽象成一个无向图G&#xff08;V,E&#xff09;&#xff0c;给定m种颜色&…

Hadoop PseudoDistributed Mode 伪分布式

Hadoop PseudoDistributed Mode 伪分布式加粗样式 hadoop101hadoop102hadoop103192.168.171.101192.168.171.102192.168.171.103namenodesecondary namenoderecource managerdatanodedatanodedatanodenodemanagernodemanagernodemanagerjob historyjob logjob logjob log 1. …

基于人工势场法的航线规划

GitHub - zzuwz/Artificial-Potential-Field: 2D平面下的人工势场法 GitHub - mellody11/Artificial-Potential-Field: 机器人导航--人工势场法及其改进 matlab2020a可以运行

Selenium元素定位之页面检测技巧

在进行web自动化测试的时候进行XPath或者CSS定位&#xff0c;需要检测页面元素定位是否正确&#xff0c;如果用脚本去检测&#xff0c;那么效率是极低的。 一般网上推选装额外的插件来实现页面元素定位检测 如&#xff1a;firebug。 其实F12开发者工具就能直接在页面上检测元…

linux上重启mysql

1、先关闭 [rootHIS bin]# ./mysqladmin -h 127.0.0.1 -u root -p shutdown 2、 再重启 [rootHIS support-files]# ./mysql.server start

Android开发知识学习——Kotlin基础

函数声明 声明函数要用用 fun 关键字&#xff0c;就像声明类要用 class 关键字一样 「函数参数」的「参数类型」是在「参数名」的右边 函数的「返回值」在「函数参数」右边使用 : 分隔&#xff0c;没有返回值时可以省略 声明没有返回值的函数&#xff1a; fun main(){println…

微信小程序上传图片和上传视频的组件失效

微信小程序上传图片和上传视频的组件失效 今天公司的小程序展示图片和视频文字的页面上传图片组件突然失效&#xff0c;之前用的好好的&#xff0c;突然所有使用都都发现用不了&#xff0c;以为是代码出现问题&#xff0c;反复查了很久。换了一个openid居然就可以了&#xff0…

jeecg-uniapp 转成小程序的过程 以及报错 uniapp点击事件

uniapp 点击事件 tap: 单击事件 confirm: 回车事件 blur:失去焦点事件 touchstart: 触摸开始事件 touchmove: 触摸移动事件。 touchend: 触摸结束事件。 longpress: 长按事件。 input: 输入框内容变化事件。 change: 表单元素值变化事件。 submit: 表单提交事件。 scroll: 滚动…

Seata入门系列【19】分布式事务之CAP、BASE理论

1 CAP理论 CAP是以下三个词语的缩写&#xff1a; Consistency&#xff1a;一致性Availability&#xff1a;可用性Partition tolerance&#xff1a;分区容忍性 CAP理论的基础概念就是在分布式系统中&#xff0c;无法同时满足以上三点。 下面我们以一个简单的分布式系统&…

如何提高Python图像表格数据提取的准确率?

Python图像表格数据提取 1、数据来源2、目标图像3、图像文本提取4、图像灰度化与二值化可以提高识别准确率吗1、数据来源 国家统计局:http://www.stats.gov.cn/sj/ 数据来源:国家统计局中国统计年鉴2022年人口数及构成 2、目标图像 数据(部分)如下: 数据形式:http://www…

docker打包container成image,然后将image上传到docker hub

第一步&#xff1a;停止正在运行的容器 docker stop <container_name> eg: docker stop xuanjie_mlir 第二步&#xff1a;将对应的container打包成image docker commit <container_id> <镜像名&#xff1a;版本> eg&#xff1a;docker commit 005672e6d97a…

MPLAB X IDE 仿真打断点提示已中断的断点?

这种中间带裂缝的是无效断点。 原因可能与XC编译器的优化有关&#xff0c;最后生成的汇编与C语言并不是一一对应的(官方给的解释是效率高)。所以这一行C语言转换的汇编代码可能并不在这个位置&#xff0c;也可能与其它汇编合并后根本就没有 我的解决方法是把优化等级调到最低&a…

导轨电表适不适合家用?

导轨电表&#xff0c;作为一种新型的电能计量设备&#xff0c;近年来在我国得到了广泛的应用。然而&#xff0c;对于家用市场来说&#xff0c;导轨电表是否适用仍然存在争议。那么&#xff0c;导轨电表适不适合家用呢&#xff1f;接下来&#xff0c;小编来为大家讲解下&#xf…

计算机网络第4章-网络层(1)

引子 网络层能够被分解为两个相互作用的部分&#xff1a; 数据平面和控制平面。 网络层概述 路由器具有截断的协议栈&#xff0c;即没有网络层以上的部分。 如下图所示&#xff0c;是一个简单网络&#xff1a; 转发和路由选择&#xff1a;数据平面和控制平面 网络层的作用…