图论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 = 3

            ArrayList<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 773

import 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;

//开始BFS
    while (!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;
    }
};

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

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

相关文章

Android和JNI交互 : 常见的图像格式转换 : NV21、RGBA、Bitmap等

1. 前言 最近在使用OpenCV处理图片的时候&#xff0c;经常会遇到需要转换图像的情况&#xff0c;网上相关资料比较少&#xff0c;也不全&#xff0c;有时候得费劲老半天才能搞定。 自己踩了坑后&#xff0c;在这里记录下&#xff0c;都是我在项目中遇到的图像转化操作&#xf…

python-机器学习-波士顿房价回归分析

一、目的 以波士顿房价数据集为对象&#xff0c;理解数据和认识数据&#xff0c;掌握梯度下降法和回归分析的初步方法&#xff0c;掌握模型正则化的一般方法&#xff0c;对回归分析的结果解读。 二、背景知识与要求 1、背景知识 波士顿房价数据集是20世纪70年代中期波士顿郊区…

ElasticSearch集群架构实战及其原理剖析

ES集群架构 为什么要使用ES集群架构 分布式系统的可用性与扩展性&#xff1a; 高可用性 服务可用性&#xff1a;允许有节点停止服务&#xff1b;数据可用性&#xff1a;部分节点丢失&#xff0c;不会丢失数据&#xff1b; 可扩展性 请求量提升/数据的不断增长(将数据分布…

【从零开始学习Redis | 第四篇】基于延时双删对Cache Aside的优化

前言&#xff1a; 在如今的单体项目中&#xff0c;为了减轻大量相同请求对数据库的压力&#xff0c;我们采取了缓存中间件Redis。核心思想为&#xff1a;把数据写入到redis中&#xff0c;在查询的时候&#xff0c;就可以直接从Redis中拿取数据&#xff0c;这样我们原本对数据库…

竞赛选题 深度学习手势检测与识别算法 - opencv python

文章目录 0 前言1 实现效果2 技术原理2.1 手部检测2.1.1 基于肤色空间的手势检测方法2.1.2 基于运动的手势检测方法2.1.3 基于边缘的手势检测方法2.1.4 基于模板的手势检测方法2.1.5 基于机器学习的手势检测方法 3 手部识别3.1 SSD网络3.2 数据集3.3 最终改进的网络结构 4 最后…

有方N58 HTTP POST 请求连接 TDengine

串口调试软件&#xff1a;格西调试精灵 第一步先注册网络获取IP地址 建立PPP连接 ATXIIC1\r PPP链路建立成功&#xff0c;查询IP地址 ATXIIC?\r 设置网络APN ATCREG?\r 运行结果&#xff0c;红线处是获…

Whisper 从0安装教程 windows

这里写自定义目录标题 Whisper 从0安装教程 windows安装过程安装python3.11安装Anaconda在Anaconda里面安装whisper安装 ffmpeg第一次运行whisper检查GPU 一些弯路 Whisper 从0安装教程 windows 因为需要把语音变成文字稿&#xff0c;问了做语言相关的朋友&#xff0c;决定使用…

结合组件库实现table组件树状数据的增删改

如图所示&#xff0c;可以实现树状数据的新增子项&#xff0c;新增平级&#xff0c;删除。主要用到了递归 代码&#xff1a; <template><el-table :data"tableData" style"width: 100%; margin-bottom: 20px" row-key"id" border def…

redis缓存击穿,redisson分布式锁,redis逻辑过期

什么是缓存击穿&#xff1a; 缓存击穿是指在高并发环境下&#xff0c;某个热点数据的缓存过期&#xff0c;导致大量请求同时访问后端存储系统&#xff0c;引起系统性能下降和后端存储压力过大的现象。 解决方案&#xff1a; 1. redisson分布式锁 本质上是缓存重建的过程中&…

selenium自动化测试入门 —— 操作元素对象

一、元素的常用操作 element.click() # 单击元素&#xff1b;除隐藏元素外&#xff0c;所有元素都可单击 element.submit() # 提交表单&#xff1b;可通过form表单元素提交表单 element.clear() # 清除元素的内容&#xff1b;如果可以的话 element.send_keys(‘需要输入的…

基于动力学模型的机械臂pid控制

参考资料&#xff1a; 一、如何实现机械臂的控制 在最常见的对机械臂动力学实现控制的问题中&#xff0c;我们会有一段机械臂末端的期望轨迹S&#xff0c;希望通过对机械臂关节处电机转矩的控制实现末端沿期望轨迹的完美运动。控制问题主要分为镇定和跟踪两种&#xff0c;上面…

LabVIEW实现变风量VAV终端干预PID控制

LabVIEW实现变风量VAV终端干预PID控制 变风量&#xff08;VAV&#xff09;控制方法的研究一直是VAV空调研究的重点。单端PID控制在温差较大时&#xff0c;系统容易出现过冲。针对空调终端单端PID控制的不足&#xff0c;设计一种干预控制与PID控制耦合的控制方法。项目使用LabV…

利用shp文件构建mask【MATLAB和ARCGIS】两种方法

1 ARCGIS &#xff08;推荐&#xff01;&#xff01;&#xff01;-速度很快&#xff09; 利用Polygon to Raster 注意&#xff1a;由于我们想要的mask有效值是1&#xff0c;在进行转换的时候&#xff0c;注意设置转换字段【Value field】 【Value field】通过编辑shp文件属性表…

el-table样式

1、实现效果&#xff0c;外部框是蓝绿色边框&#xff0c;深色背景&#xff0c;里面的表格首先设置透明色&#xff0c;然后应用自定义斑马纹。 2、代码 template代码&#xff0c;其中样式frameBordStyle是深色背景框&#xff0c;不负责表格样式&#xff0c;表格样式由tableStyl…

OSG多视口创建:osgViewer::CompositeViewer

1、效果 在osg的实际应用场景中&#xff0c;有时候需要同时创建多个场景视图&#xff0c;并保证各个场景视图中有不一样的显示和操作&#xff1a;例如&#xff1a;漫游器、照相机、粒子效果、多个模型组合等。此时就要用到OSG提供的osgViewer::CompositeViewer类来实现这个需求…

零信任网络:一种全新的网络安全架构

随着网络技术的不断发展&#xff0c;网络安全问题日益凸显。传统的网络安全策略往往基于信任和验证&#xff0c;但这种信任策略存在一定的局限性。为了解决这一问题&#xff0c;零信任网络作为一种全新的网络安全架构&#xff0c;逐渐受到人们的关注。本文将对零信任网络的概念…

推荐PHP付费进群源码

PHP付费进群源码带自动定位基于ThinkPHP框架开发的&#xff0c;可以快速搭建知识付费粉丝进群。 更新&#xff1a; 1.首页付款轮播 2.城市定位功能 3.更新及优化域名库及支付设置 4.新增一张图模板设置模式&#xff0c;简化后台模板设置 5.前后台其他优化 演示地址&#xff1a…

centos7部署nginx

CentOS7安装Nginx-1.16.1稳定版 小白教程&#xff0c;一看就会&#xff0c;一做就成。 1.安装依赖环境 yum -y install gcc gcc-c automake pcre pcre-devel zlib zlib-devel openssl openssl-devel 2.下载安装包&#xff08;不能联网的不行&#xff09;&#xff0c;可以留言…

电路正负反馈,电压电流反馈,串并联反馈详细判别方法

正/负反馈&#xff1a;假设输出升高&#xff0c;转一圈回来仍使其升高就是正反馈&#xff0c;反之就是负反馈。作图法&#xff1a;在RL的信号端画一个向上的小箭头&#xff0c;沿着反馈环路&#xff0c;每经过一个元器件就画一个相应的箭头&#xff0c;一直画到放大器的输出端&…

计算机组成与结构-安全性和可靠性

系统可靠性分析 概念 平均无故障时间 MTTF 1/失效率 平均故障修复时间 MTTR1/修复率 平均故障间隔时间 MTBFMTTFMTTR 系统可用性 MTTF/(MTTFMTTR)*100% 计算 串联系统 一个设备不可靠&#xff0c;整个系统崩溃RR1R2Rn 并联系统 所有设备不可靠&#xff0c;整个系统崩溃R1-(1…