Java实现 LeetCode 773 滑动谜题（BFS）

773. 滑动谜题

在一个 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] 的排列.

PS:

BFS搜索，交换，然后每一次都看是不是匹配

class Solution {

    private static int ROW = 2;

    private static int COL = 3;

    private static final String RESULT = "123450";

    Set<String> set;

    LinkedList<String> queue;

    public int slidingPuzzle(int[][] board) {

    	if ((board.length != ROW) || (board[0].length != COL)) {

    		return 0;

    	}

    	set = new HashSet<>();

    	int time = 0;

    	char[] boardStr = getCharFromBoard(board);

    	if (RESULT.equals(Arrays.toString(boardStr))) {

    		return 0;

    	}

    	queue = new LinkedList<>();

    	queue.addLast(new String(boardStr));

    	while (!queue.isEmpty()) {

    		int size = queue.size();

    		for (int i = 0; i < size; i++) {

    			String node = queue.pollFirst();

    			if (RESULT.equals(node)) {

    				return time;

    			}

    			boardStr = node.toCharArray();

    			if (boardStr[0] == '0') {

    				move(boardStr, 0, 1);

    				move(boardStr, 0, 3);

    			} else if (boardStr[1] == '0') {

    				move(boardStr, 1, 0);

    				move(boardStr, 1, 2);

    				move(boardStr, 1, 4);

    			} else if (boardStr[2] == '0') {

    				move(boardStr, 2, 1);

    				move(boardStr, 2, 5);

    			} else if (boardStr[3] == '0') {

    				move(boardStr, 3, 0);

    				move(boardStr, 3, 4);

    			} else if (boardStr[4] == '0') {

    				move(boardStr, 4, 1);

    				move(boardStr, 4, 3);

    				move(boardStr, 4, 5);

    			} else if (boardStr[5] == '0') {

    				move(boardStr, 5, 2);

    				move(boardStr, 5, 4);

    			}

    		}

    		time++;

    	}

    	return -1;

    }

    private void move(char[] string, int i, int j) {

		swap(string, i, j);

		String str = new String(string);

		if (!set.contains(str)) {

			queue.addLast(str);

			set.add(str);

		}

		swap(string, i, j);

    }

    private void swap (char[] string, int i, int j) {

    	char temp = string[i];

    	string[i] = string[j];

    	string[j] = temp;

    }

    private char[] getCharFromBoard(int[][] board) {

    	char[] res = new char[6];

    	res[0] = (char) ('0' + board[0][0]);

    	res[1] = (char) ('0' + board[0][1]);

    	res[2] = (char) ('0' + board[0][2]);

    	res[3] = (char) ('0' + board[1][0]);

    	res[4] = (char) ('0' + board[1][1]);

    	res[5] = (char) ('0' + board[1][2]);

    	return res;

    }

}

巴特西

Java实现 LeetCode 773 滑动谜题（BFS）

773. 滑动谜题

最新文章

热门文章