南海最新消息,seo的方法,南川网站建设,高邮城乡建设局网站文章目录 状态的表达例题1题解1 终止条件#xff1a;有一个数位为42 状态的改变#xff1a;a表示十位数#xff0c;b表示个位数3 其他设置 例题2 力扣773 滑动谜题JavaC 状态的表达
例题1 从初始的(x#xff0c;y)状态#xff0c;到最后变成#xff08;4#xff0c;有一个数位为42 状态的改变a表示十位数b表示个位数3 其他设置 例题2 力扣773 滑动谜题JavaC 状态的表达
例题1 从初始的(xy)状态到最后变成4或者4.
本道题对于(xy)的状态可以使用10xy进行表达也就是变成了一个数字分别放在不同的数位上。 但是本状态的表示方法不适用单个数组超过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];队列用于记录访问的每个节点的状态
QueueInteger 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(){QueueInteger 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 3ArrayListInteger 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 IterableInteger result(){ArrayListInteger 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) {QueueString queue new LinkedList();HashMapString, 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();ArrayListString 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 ArrayListString getNexts(String s){int[][] cur stringToBoard(s);int zero;for(zero 0; zero 6; zero )if(cur[zero / 3][zero % 3] 0)break;ArrayListString 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(vectorvectorint 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);}}//构造队列并初始化queuestring q{{init}};//设置unordered_set记录访问状态unordered_setstring 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();}//对头出队的时候开始移动到下一个状态因此步数1ans;}return -1;}
};
