bfs 解空间
题目描述
给定一个只还有0~7状态空间，求解给定空间转换到目标空间01234567的最少步数。规定只有零状态可与相邻格子移动（up,down,left,right）。
分析
解法一
既然是求解最少步数，根据题意能得到的最直观的解法是bfs，即对于给定的每个状态进行一次bfs从给定状态start到goal的广搜。
1
2
3
4
| for i in casenum:
cin>>state
minstep = bfs(state,goal)
cout<<minstep
|
以上伪代码在casenum较少时是可行的，用上述思想是不能通过题目的。
解法二
对于解法一中给定的每个状态state，都从state出发到goal，必定会有重复状态的遍历。
可以想到，从每个状态到目标状态的最短路径与从目标状态到给定状态求解的路径是一致的，因此可以采用从目标状态goal逆向bfs，求解到可到达状态的最短路径，即遍历一次解空间，此后直接查询结果即可。
具体过程
定义状态
每个状态包括当前0~7的状态，以及0的位置，因此使用结构体
1
2
3
4
| struct State{
int state[2][4];
int x,y,step;
};
|
状态去重
因为每个状态只有八位且为数字，因此可用整形映射。
1
2
3
4
5
6
7
8
9
| int encode(int state[][4]){
int res=0;
for(int i=0;i<2;i++){
for(int j=0;j<4;j++){
res=res*10+state[i][j];
}
}
return res;
}
|
具体求解
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
|
#include <bits/stdc++.h>
#define ll long long int
#define inf 0x3f3f3f3f
#define LOCAL
#define min(a, b) a < b ? a : b
using namespace std;
const int maxn = 1e5 + 5;
int ss[2][4];
int goal[2][4] = {8, 1, 2, 3, 4, 5, 6, 7};
int goalCode = 81234567;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
struct Map
{
int state[2][4];
int step;
int x, y;
};
int encode(int x[][4])
{
int res = 0;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 4; j++)
{
res = res * 10 + x[i][j];
}
}
return res;
}
void decode(int x, int y[][4])
{
for (int i = 1; i >= 0; i--)
{
for (int j = 3; j >= 0; j--)
{
y[i][j] = x % 10;
x /= 10;
}
}
}
typedef Map node;
map<int, int> mins;
#define DEBUG
void bfs()
{
queue<node> q;
node st;
memcpy(st.state, goal, sizeof(goal));
st.x = st.y = 0;
st.step = 1;
mins[goalCode] = 1;
q.push(st);
while (!q.empty())
{
node f = q.front();
q.pop();
for (int i = 0; i < 4; i++)
{
int fx = f.x + dx[i];
int fy = f.y + dy[i];
if (fx >= 0 && fy >= 0 && fx < 2 && fy < 4)
{
node t = f;
swap(t.state[fx][fy], t.state[f.x][f.y]);
int coded = encode(t.state);
t.x = fx;
t.y = fy;
if (!mins[coded])
{
mins[coded] = ++t.step;
q.push(t);
}
}
}
}
}
void solve()
{
int x;
bfs();
while (scanf("%d", &x) != EOF)
{
ss[0][0] = x;
if (x == 0)
{
ss[0][0] = 8;
}
int start = 0, end = 0;
for (int i = 1; i <= 7; i++)
{
scanf("%d", &ss[i / 4][i % 4]);
if (ss[i / 4][i % 4] == 0)
{
ss[i / 4][i % 4] = 8;
start = i / 4;
end = i % 4;
}
}
printf("%d\n", mins[encode(ss)] - 1);
}
}
int main()
{
#ifdef LOCAL
freopen("in.in", "r", stdin);
#endif
solve();
return 0;
}
|
