八数码问题 Sliding Puzzle II

Java

public class Solution {
    /**
     * @param init_state: the initial state of chessboard
     * @param final_state: the final state of chessboard
     * @return: return an integer, denote the number of minimum moving
     */
		public int minMoveStep(int[][] init_state, int[][] final_state) {
				String source = matrixToString(init_state);
				String target = matrixToString(final_state);
		
				Queue<String> queue = new LinkedList<String>();
				Set<String> set = new HashSet<String>();
		
				queue.offer(source);
				set.add(source);
		
				int result = 0;
				while (!queue.isEmpty()) {
					int n = queue.size();
					for (int i = 0; i < n; i++) {
						String cur = queue.poll();
						if (cur.equals(target)) {
							return result;
						}
						
						for (String next : getNext(cur)) {
							if (!set.contains(next)) {
								queue.offer(next);
								set.add(next);
							}
						}
					}
					result += 1;
				}
				return -1;
		}

private String matrixToString(int[][] state) {
StringBuffer sb = new StringBuffer();
for (int i = 0; i < 3; ++i) {
			for (int j = 0; j < 3; ++j) {
				sb.append(state[i][j]);	
			}
}
return sb.toString();
}

//字符串的下标和矩阵的位置转换
private List<String> getNext(String cur) {
		List<String> result = new ArrayList<>();
		
		int zeroIndex = cur.indexOf('0');
		int cx = zeroIndex / 3;
		int cy = zeroIndex % 3;              //字符串index 转换到矩阵坐标套路
		
		int[] dx = {0, 0, 1, -1};
		int[] dy = {1, -1, 0, 0};
		
		for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i]; //遍历到下一个坐标
				if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
				
				char[] chars = cur.toCharArray();
				chars[zeroIndex] = chars[nx * 3 + ny];
				chars[nx * 3 + ny] = '0';
				result.add(new String(chars));
		}
		return result;
		}
}