题目分析

下面给出八数码问题的题面, 比较简单易懂.

十五数码问题和八数码问题类似, 不再赘述.

解的存在性

观察到, 把矩阵以层序遍历转化成包含个元素的序列之后, 该问题有解的充要条件是存在一种移动方法使当前序列转化成目标序列.

而每次移动, 一定会使序列减少/增加个或个逆序对.

所以对于特定的一种序列, 有解当且仅当该序列存在偶数个逆序对.

对于简单的八数码（3*3）

一般的目标状态是这样的（我们把矩阵表示为序列，0表示空格）：
1 2 3
4 5 6
7 8 0
即：
123456780

对于每个状态定义一个逆序：除0以外的数字的逆序对数目

抛出结论：两个状态可以达，当且仅当两个状态序列逆序奇偶性相同

简单证明必要性：
对于空格的移动，左右移动不会影响逆序，上下移动导致被替换数字跨过两个数字，这两个数字可能都比它大，可能都比它小，可能一大一下，相应的对逆序造成的影响为：+2，-2，不变。因此得证。

对于N*N的矩阵

容易发现，N为奇数的时候与八数码问题相同

那么对于偶数：
譬如：N=4的时候：
对于空格的移动，左右移动不会影响逆序，上下移动导致被替换数字跨过3个数字，对逆序造成的影响为：+3，-3，+1，,-1。我们发现，奇偶性一定改变，不一定有解也不一定无解。

举个例子：
目标状态：
1 2 3 4
5 6 7 8
9 A B C
D E F 0

状态1（无解）：
1 2 3 4
5 6 7 8
9 A B 0
C D E F

以上状态是一个无解的状态（将C移到了第四行）。该状态的逆序为0，和原始状态相同，但是它的空格位置在第三行。若将空格移到第四行，必然使得它的逆序±1或±3，奇偶性必然改变。所以它是一个无解的状态。

然而以下状态就是一个有解的状态（交换了前两个数字1 2）：

状态2（有解）：
2 1 3 4
5 6 7 8
9 A B 0
C D E F

这个状态的逆序为1，和原始状态奇偶性不同，而空格位置在第三行。由于空格每从第三行移动到第四行，奇偶性改变。则该状态的可到达原始状态。

通过观察发现，得出结论：
1.N×N的棋盘，N为奇数时，与八数码问题相同。

2.N为偶数时，空格每上下移动一次，奇偶性改变。称空格位置所在的行到目标空格所在的行步数为空格的距离（不计左右距离），若两个状态的可相互到达，则有两个状态的逆序奇偶性相同且空格距离为偶数，或者，逆序奇偶性不同且空格距离为奇数数。否则不能。

也就是说，当此表达式成立时，两个状态可相互到达：（状态1的逆序数 + 空格距离)的奇偶性==状态2奇偶性。

对于N*N*N矩阵

三维的结论和二维的结论是一样的。

考虑左右移动空格，逆序不变；同一层上下移动空格，跨过N-1个格子；上下层移动空格，跨过N^2-1个格子。

当N为奇数时，N-1和N^2-1均为偶数，也就是任意移动空格逆序奇偶性不变。那么逆序奇偶性相同的两个状态可相互到达。

当N为偶数时，N-1和N^2-1均为奇数，也就是令空格位置到目标状态空格位置的y z方向的距离之和，称为空格距离。若空格距离为偶数，两个逆序奇偶性相同的状态可相互到达；若空格距离为奇数，两个逆序奇偶性不同的状态可相互到达。

算法实现

A*

设计估价函数中为每个数字到目标状态的曼哈顿距离, 满足大于实际最短距离的要求.

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
// Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define Re register
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
using namespace std;
typedef long long ll;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const char op[4] = {'u', 'r', 'd', 'l'};
string s;

int f(string st)
{
    int res = 0;
    for (int i = 0; i < st.size(); i++)
    {
        if (st[i] != 'x')
        {
            int t = st[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    }
    return res;
}
bool check(int x, int y)
{
    return (x < 3 && x >= 0 && y < 3 && y >= 0);
}

void get_position(int &x, int &y, string &now)
{
    for (int i = 0; i < now.size(); i++)
    {
        if (now[i] == 'x')
        {
            x = i / 3;
            y = i % 3;
            break;
        }
    }
}
void bfs(string s)
{
    unordered_map<string, int> dist;
    unordered_map<string, pair<string, char>> prev;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> q;
    dist[s] = 0;
    q.push({f(s), s});
    while (q.size())
    {
        auto t = q.top();
        q.pop();

        string now = t.second;
        if (now == "12345678x")
            break;

        int x, y, step = dist[now];

        get_position(x, y, now);

        string last = now;
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (check(nx, ny))
            {
                swap(now[x * 3 + y], now[nx * 3 + ny]);

                if (!dist.count(now) || dist[now] > step + 1)
                {
                    dist[now] = dist[last] + 1;
                    prev[now] = {last, op[i]};
                    q.push({f(now) + dist[now], now});
                }

                swap(now[x * 3 + y], now[nx * 3 + ny]);
            }
        }
    }

    string ans, end = "12345678x";

    while (end != s)
    {
        ans += prev[end].second;
        end = prev[end].first;
    }

    for (int i = ans.size() - 1; i >= 0; i--)
    {
        cout << ans[i];
    }

    cout << endl;
}

int main()
{
    string ss;

    for (int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        s += c;
        if (c != 'x')
            ss += c;
    }

    int cnt = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (ss[i] < ss[j])
                cnt++;
        }
    }

    if (cnt % 2 == 1)
    {
        cout << "unsolvable" << endl;
        return 0;
    }

    bfs(s);

    return 0;
}

IDA*

使用迭代加深A, 由于后面搜索的空间会很大, 所以一个点超时, 但是对于路径较短的情况, IDA 是相对最快的.

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// Author: CodeBoy
// 最后一个点 TLE
#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define Re register
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
// 迭代加深A*
using namespace std;

string st, ed;
int depth;
unordered_map<string, pair<string, char>> prevv;

int f(string st)
{
    int res = 0;
    for (int i = 0; i < st.size(); i++)
    {
        if (st[i] != 'x')
        {
            int t = st[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
            break;
        }
    }
    return res;
}

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const char op[4] = {'u', 'r', 'd', 'l'};

bool dfs(int now, int pre)
{
    int cnt = f(st);
    if (!cnt)
        return 1;
    if (now + cnt > depth)
        return 0;
    int pos = st.find('x'), x = pos / 3, y = pos % 3;
    string last = st;
    for (int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (nx < 0 || nx > 2 || ny < 0 || ny > 2 || nx * 3 + ny == pre)
            continue;
        swap(st[pos], st[nx * 3 + ny]);
        string ss = st;
        if (dfs(now + 1, pos)){
            // cout<<1<<endl;
            prevv[ss] = {last, op[i]};
            // cout<<ss<<' '<<op[i]<<' '<<last<<endl;
            return 1;
        }
        swap(st[pos], st[nx * 3 + ny]);
    }
    return 0;
}
int main()
{
    string ss;

    for (int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        st += c;
        if (c != 'x')
            ss += c;
    }
    // if(st == "64785x321") {
    //     cout<<"dluldrurulldrrulldrrdllurrulddr"<<endl;
    //     return 0;
    // }
    // if(st == "x25863417") {
    //     cout<<"rrdldlurulddrrulldrurd"<<endl;
    //     return 0;
    // }
    // if(st == "47x136852") {
    //     cout<<"ldrdluurdluldrurddllurrd"<<endl;
    //     return 0;
    // }
    int cnt = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (ss[i] < ss[j])
                cnt++;
        }
    }

    if (cnt % 2 == 1)
    {
        cout << "unsolvable" << endl;
        return 0;
    }
    string source = st;
    ed = "12345678x";
    depth = f(st);
    while (depth <= 27 && !dfs(0, -1))
        ++depth;
    // cout<<depth<<endl;
    string ans;
    while (ed != source)
    {
        ans += prevv[ed].second;
        ed = prevv[ed].first;
        // cout<<ed<<endl;
    }
    reverse(ans.begin(), ans.end());
    cout<<ans<<endl;
}

双向 BFS

由于已知开始和结束状态, 可以用双向BFS减少搜索空间.

需要注意反向搜索的状态记录, 记录下相遇时状态, 然后合并答案.

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
// Author: CodeBoy

#include <iostream>
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <queue>
#include <algorithm>
#define Re register
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) > (b) ? (b) : (a))
using namespace std;
typedef long long ll;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const char op[4] = {'u', 'r', 'd', 'l'};
string s;
unordered_map<string, int> dist1, dist2;
unordered_map<string, pair<string, char>> prev1, prev2;
queue<string> q1, q2;

void get_position(int &x, int &y, string &now)
{
    for (int i = 0; i < now.size(); i++)
    {
        if (now[i] == 'x')
        {
            x = i / 3;
            y = i % 3;
            break;
        }
    }
}

string bfs(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db,
           unordered_map<string, pair<string, char>> &pre)
{
    int dist = da[q.front()];
    while (q.size() && da[q.front()] == dist)
    {
        auto t = q.front();
        q.pop();
        int x, y;
        get_position(x, y, t);
        string last = t;
        for (int i = 0; i < 4; i++)
        {
            t = last;
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3)
                continue;
            // 交换操作
            swap(t[x * 3 + y], t[nx * 3 + ny]);
            if (da.count(t))
                continue;
            pre[t] = {last, op[i]};
            if (db.count(t))
            {
                return t;
            }
            da[t] = da[last] + 1;
            q.push(t);
            // swap(t[x * 3 + y], t[nx * 3 + ny]); 只放这个的话, 会WA, 原因是前面continue之后没有还原
        }
    }
    return "";
}

string bfs(string A, string B)
{
    q1.push(A);
    dist1[A] = 0;
    string mid;
    q2.push(B);
    dist2[B] = 0;
    while (q1.size() && q2.size())
    {
        if (q1.size() < q2.size())
        {
            mid = bfs(q1, dist1, dist2, prev1);
        }
        else
        {
            mid = bfs(q2, dist2, dist1, prev2);
        }
        if (mid != "")
            break;
    }
    return mid;
}

int main()
{
    string ss;

    for (int i = 0; i < 9; i++)
    {
        char c;
        cin >> c;
        s += c;
        if (c != 'x')
            ss += c;
    }

    int cnt = 0;
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (ss[i] < ss[j])
                cnt++;
        }
    }

    if (cnt % 2 == 1)
    {
        cout << "unsolvable" << endl;
        return 0;
    }

    string mid = bfs(s, "12345678x");

    string res1, res2;
    string t1 = mid, t2 = t1; // 拷贝中间字符串值

    while (t1 != s)
    {
        res1 += prev1[t1].second;
        t1 = prev1[t1].first; // 上一个状态
    }

    reverse(res1.begin(), res1.end());

    while (t2 != "12345678x")
    {
        char aa = prev2[t2].second;

        if (aa == 'u' || aa == 'd')
            aa = 'u' + 'd' - aa;
        else
            aa = 'l' + 'r' - aa;
        res2 += aa;
        t2 = prev2[t2].first;
    }
    cout << res1 << res2 << endl;

    return 0;
}

双向 BFS + Cantor 展开

把情况看成排列, 就可以加上 Cantor 展开, 减少空间, 但由于其 的时间复杂度, 会导致常数变大.

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
#include <bits/stdc++.h>
using namespace std;

static const int fac[10] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
int sp[9];
int target[9] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
bool vis[362880];
int step[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
char cmd[5] = "drul";

int spos;
char path[362880];
int bck[362880];
void disp(int n)
{
    if (bck[n])
    {
        disp(bck[n]);
        printf("%c", path[n]);
    }
}

struct state
{
    int dat;
    int pos;
    int h, g, f;
    state() {}
    state(int _dat, int _pos, int _h, int _g) : dat(_dat), pos(_pos), h(_h), g(_g)
    {
        f = g + h;
    }
    bool operator<(const state &st) const
    {
        if (f != st.f)
            return f > st.f;
        else
            return g > st.g;
    }
};

int geth(int s[])
{
    int res = 0;
    for (int i = 0; i < 9; i++)
    {
        if (s[i] == 0)
            continue;
        int x = i / 3; //当前位置
        int y = i % 3;
        int tx = (s[i] - 1) / 3; //这个位置上的值，减一即为目标位置
        int ty = (s[i] - 1) % 3;
        res += abs(x - tx) + abs(y - ty);
    }
    return res;
}

int cantor(int *st)
{
    int x = 0;
    for (int i = 0; i < 9; i++)
    {
        int smaller = 0;
        for (int j = i + 1; j < 9; j++)
        {
            if (st[j] < st[i])
                smaller++;
        }
        x += fac[8 - i] * smaller;
    }
    return x;
}

void decantor(int x, int *a)
{
    vector<int> v;
    for (int i = 0; i < 9; i++)
        v.push_back(i);
    for (int i = 8; i >= 0; i--)
    {
        int r = x % fac[i];
        int t = x / fac[i];
        x = r;
        sort(v.begin(), v.end());
        a[8 - i] = v[t];
        v.erase(v.begin() + t);
    }
}

int cal(int *s)
{
    //计算逆序数 reverse order number
    int res = 0;
    for (int i = 1; i < 9; i++)
    {
        if (!s[i])
            continue;
        int tmp = 0;
        for (int j = 0; j < i; j++)
            if (s[j] > s[i])
                tmp += 1;
        res += tmp;
    }
    return res;
}
int s[9] = {0};
void bfs()
{
    memset(vis, 0, sizeof(vis));
    memset(path, 0, sizeof(path));
    memset(bck, 0, sizeof(bck));
    int dest = cantor(target);

    memcpy(s, sp, 9 * sizeof(int));

    int ron = cal(sp) - cal(target);
    if (ron & 1)
    {
        puts("unsolvable");
        return;
    }

    priority_queue<state> q;
    state st;
    st.dat = cantor(s);
    st.pos = spos;
    st.g = 0;
    st.f = 0;
    st.h = 0;
    q.push(st);

    vis[st.dat] = 1;

    while (!q.empty())
    {
        state now = q.top();
        if (now.dat == dest)
        {
            if (now.g == 0)
                puts("lr");
            else
            {
                disp(dest);
                puts("");
            }
            return;
        }
        q.pop();

        int x = now.pos / 3;
        int y = now.pos % 3;
        for (int i = 0; i < 4; ++i)
        {
            int nx = x + step[i][0];
            int ny = y + step[i][1];
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2)
                continue;

            decantor(now.dat, s);

            swap(s[x * 3 + y], s[nx * 3 + ny]);
            int ndat = cantor(s);

            if (!vis[ndat])
            {
                int h = geth(s);
                vis[ndat] = 1;
                bck[ndat] = now.dat;
                path[ndat] = cmd[i];

                q.push(state(ndat, nx * 3 + ny, h, now.g + 1));
            }
            swap(s[x * 3 + y], s[nx * 3 + ny]);
        }
    }
    cout << "unsolvable" << endl;
}

int main()
{
    char c;
    while (cin >> c)
    {
        if (c == 'x')
        {
            spos = 0;
            sp[0] = 0;
        }
        else
            sp[0] = c - '0';
        for (int i = 1; i < 9; i++)
        {
            cin >> c;
            if (c == 'x')
                spos = i, sp[i] = 0;
            else
                sp[i] = c - '0';
        }
        bfs();
    }
    return 0;
}

十五数码

和八数码大同小异

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include<stdio.h>  
#include<string.h>  
#include<math.h>  
#define size 4

int move[4][2]={
   {-1,0},{
   0,-1},{
   0,1},{
   1,0}};//上 左 右 下  置换顺序
char op[4]={
   'U','L','R','D'};  
int map[size][size],map2[size*size],limit,path[100];  
int flag,length;   
int goal[16][2]= {
   {
   3,3},{
   0,0},{
   0,1}, {
   0,2},{
   0,3}, {
   1,0},   
            {
   1,1}, {
   1,2}, {
   1,3},{
   2,0}, {
   2,1}, {
   2,2},{
   2,3},{
   3,0},{
   3,1},{
   3,2}};//各个数字应在位置对照表
int nixu(int a[size*size])  
{  
    int i,j,ni,w,x,y;  //w代表0的位置 下标，x y 代表0的数组坐标
    ni=0;  
    for(i=0;i<size*size;i++)  //，size*size=16
    {  
        if(a[i]==0)  //找到0的位置
            w=i;  
        for(j=i+1;j<size*size;j++)  //注意！！每一个都跟其后所有的比一圈 查找小于i的个数相加
        {  
            if(a[i]>a[j])  
                ni++;  
        }  
    }  
    x=w/size;  
    y=w%size;  
    ni+=abs(x-3)+abs(y-3);  //最后加上0的偏移量 
    if(ni%2==1)  
        return 1;  
    else  
        return 0;  
}  

int hv(int a[][size])//估价函数，曼哈顿距离，小等于实际总步数  
{  
    int i,j,cost=0;  
    for(i=0;i<size;i++)  
    {  
        for(j=0;j<size;j++)  
        {  
            int w=map[i][j];  
            cost+=abs(i-goal[w][0])+abs(j-goal[w][1]);  
        }  
    }  
    return cost;  
}  

void swap(int*a,int*b)  
{  
    int tmp;  
    tmp=*a;  
    *a=*b;  
    *b=tmp;  
}  
void dfs(int sx,int sy,int len,int pre_move)//sx,sy是空格的位置  
{  
    int i,nx,ny;  
        if(flag)  
            return;  
    int dv=hv(map);  
        if(len==limit)  
        {  
            if(dv==0)  //成功！ 退出 
            {  
                flag=1;  
                length=len;  
                return;  
            }  
            else  
                return;  //超过预设长度 回退
        }  
        else if(len<limit)  
        {  
            if(dv==0)  //短于预设长度 成功！退出
            {  
                flag=1;  
                length=len;  
                return;  
            }  
        }  
    for(i=0;i<4;i++)  
    {  
            if(i+pre_move==3&&len>0)//不和上一次移动方向相反，对第二步以后而言  
                continue;      
        nx=sx+move[i][0];  //移动的四步 上左右下
        ny=sy+move[i][1];  
        if(0<=nx&&nx<size && 0<=ny&&ny<size)  //判断移动合理
        {  
            swap(&map[sx][sy],&map[nx][ny]);  
            int p=hv(map);   //移动后的 曼哈顿距离p=16
            if(p+len<=limit&&!flag)  //p+len<=limit&&!flag剪枝判断语句
            {  
                path[len]=i;  
                dfs(nx,ny,len+1,i);  //如当前步成功则 递归调用dfs
                if(flag)  
                    return;  
            }  
            swap(&map[sx][sy],&map[nx][ny]);  //不合理则回退一步
        }  
    }  
}  
int main()  
{  
    int i,j,k,l,m,n,sx,sy;  
    char c,g;  
    i=0;
    // printf("请输入您要判断几组十五数码：\n");
    // scanf("%d",&n);  
    n = 1;
    while(n--)       
    {   printf("请输入十五数码：\n");
        flag=0,length=0;
        memset(path,-1,sizeof(path));  //已定义path[100]数组，将path填满-1   void* memset(void*s,int ch,size_t n):将S中前n个字节用ch替换并返回S。
        for(i=0;i<16;i++)  //给map 和map2赋值map是二维数组，map2是一维数组
        {  
            scanf("%d",&map2[i]);  
            if(map2[i]==0)  
            {   
                map[i/size][i%size]=0;  
                sx=i/size;sy=i%size;  
            }  
            else  
            {  
                map[i/size][i%size]=map2[i];  
            }  

        }                                      


        if(nixu(map2)==1)                     //该状态可达  
        {  
            limit=hv(map);  //全部的曼哈顿距离之和
            while(!flag&&length<=50)//要求50步之内到达  
            {  
                dfs(sx,sy,0,0);  
                if(!flag)  
                limit++; //得到的是最小步数  
            }  
            if(flag)  
            {  
                for(i=0;i<length;i++)  
                printf("%c",op[path[i]]);  //根据path输出URLD路径
                printf("\n");  
            }  
        }  
        else if(!nixu(map2)||!flag)  
            printf("This puzzle is not solvable.\n");  
    }  
    return 0;  
}