'lintcode 滑动拼图'

Posted on | In

描述

在一块大小为 2x3 的板上，有 5 块瓦片，分别用整数 1 到 5 表示，还有一块空地用 0 表示。

一次移动表示 0 与其相邻的四个方向之一的数字交换位置。

当且仅当 这块板 上的瓦片摆放状态为 [[1,2,3],[4,5,0]] 时，才能说这块板存在的问题被解决了。

board 会以上面讲的 2 x 3 大小的数组形式输入 。
board[i][j] 会是 [0, 1, 2, 3, 4, 5] 中的其中一个值.

样例

给出 board = [[1,2,3],[4,0,5]], 返回 1.

结束:
交换0和5，只需要一步.
给出 board = [[1,2,3],[5,4,0]], 返回 -1.

解释:
不管移动多少步都无法解决问题。
给出 board = [[4,1,2],[5,0,3]], 返回 5.

解释:
至少需要移动5步来解决这个问题。
比如这么做:
移动 0 步之后: [[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.

思路

使用bfs，把二维数组转化为string来存到队列当中，每次都对队列里面的所有元素进行遍历，如果是目标就返回，如果不是就把下一步所有的情况排到队列当中，设置一个set来判断状态是否已经判断过，防止无限循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
    /**
     * @param board: the given board
     * @return:  the least number of moves required so that the state of the board is solved
     */
    string vector2string(vector<vector<int>> v) {
        string res(6, '0');
        int j = 0;
        for (int i = 0; i < 2; i++) {
		    for (int k = 0; k < 3; k++) {
			    res[j] = v[i][k] + '0';
			    j++;
		    }
	    }
	    return res;
    }

    vector<vector<int>> string2vector(string tar){
        vector<vector<int>> v(2, vector<int>(3,0));
	    int j = 0;
	    for (int i = 0; i < 2; i++) {
		    for (int k = 0; k < 3; k++) {
			    v[i][k] = tar[j] - '0';
			    j++;
		    }
	    }
	    return v;
    }

    int slidingPuzzle(vector<vector<int>> &board) {
        // write your code here
        string target = "123450" , cur = vector2string(board);
        vector<vector<int>> move = {{1,0},{0,1},{0,-1},{-1,0}};
        unordered_set<string> s;
        s.insert(cur);
        queue<string> q;
        q.push(cur);
        int res = 0;
        while (!q.empty()) {
            res++;
            int n = q.size();
            while (n > 0) {
                string temp = q.front();
                q.pop();
                if (temp == target)
                    return res-1;
                vector<vector<int>> v = string2vector(temp);
                int pos_x, pos_y;
                for (int i = 0; i < 2; i++) {
                    for (int j = 0; j < 3; j++) {
                        if (v[i][j] == 0) {
                            pos_x = i;
                            pos_y = j;
                            break;
                        }
                    }
                }
                for (int i = 0; i < 4; i++){
                    int new_pos_x = pos_x + move[i][0],
                        new_pos_y = pos_y + move[i][1];
                    if (new_pos_x >= 0 && new_pos_x <=1 && new_pos_y >= 0 && new_pos_y <= 2) {
                        vector<vector<int>> new_v = v;
                        swap(new_v[pos_x][pos_y], new_v[new_pos_x][new_pos_y]);
                        string str = vector2string(new_v);
                        if (s.find(str) == s.end()) {
                            q.push(str);
                            s.insert(str);
                        }
                    }
                }
                n--;

            }
        }
        return -1;
    }
};
-------------end of filethanks for reading-------------