台州制作网站软件,怎么查询网站开发公司,做五金建材市场的网站,广州建设工程交易中心主管部门题目
在一个 2 x 3 的板上#xff08;board#xff09;有 5 块砖瓦#xff0c;用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字#xff08;上下左右#xff09;进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。…题目
在一个 2 x 3 的板上board有 5 块砖瓦用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字上下左右进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态返回最少可以通过多少次移动解开谜板如果不能解开谜板则返回 -1 。
示例
输入board [[1,2,3],[4,0,5]]
输出1
解释交换 0 和 5 1 步完成
输入board [[1,2,3],[5,4,0]]
输出-1
解释没有办法完成谜板
输入board [[4,1,2],[5,0,3]]
输出5
解释
最少完成谜板的最少移动次数是 5
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入board [[3,2,4],[1,5,0]]
输出14提示
board 是一个如上所述的 2 x 3 的数组.board[i][j] 是一个 [0, 1, 2, 3, 4, 5] 的排列.
解题思路
使用字符串代表谜板的状态
board [[1,2,3],[4,0,5]]1 2 3
4 0 5使用字符串 123405表示所以每一个字符串就代表谜板的一个状态
广度优先搜索 利用队列实现广度优先搜索根据0所在位置将0和周围的数字进行交换从而衍生出若干种情况加入队列
代码
class Solution {public void swagg(char[] tar,int x,int y) {char temptar[x];tar[x]tar[y];tar[y]temp;}public int slidingPuzzle(int[][] board) {StringBuilder stringBuildernew StringBuilder();for (int i0;iboard.length;i)for (int j0;jboard[0].length;j){stringBuilder.append(board[i][j]);}SetString setnew HashSet();QueueString queuenew LinkedList();queue.add(stringBuilder.toString());int res0;String snull;while (!queue.isEmpty()){int curqueue.size();for (int i0;icur;i){s queue.poll();if(s.equals(123450)) return res;char[] ths.toCharArray();for (int j0;j6;j){if(th[j]0){int xj%3,yj/3;if(y1){swagg(th,j,x);String tempnew String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,x);}else {swagg(th,j,x3);String tempnew String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,x3);}if(x0){swagg(th,j,j-1);String tempnew String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,j-1);}if(x2){swagg(th,j,j1);String tempnew String(th);if(!set.contains(temp))queue.add(temp);set.add(temp);swagg(th,j,j1);}}}}res;}return -1;}
}
