Flood Fill
- 优点：可以在线性时间内找到某个点所在的联通块；
池塘计数
1 |
|
城堡问题
1 | //可以用位数是否为1判断该位置是否存在墙; |
山峰和山谷
1 |
|
最短路模型
BFS，当边权重一样的时候便可以用bfs找到最短路，是dijkstra算法的特例；dijkstra是用堆来维护队列，每次取出最小值；当全部边的权重都是1，则是按照层的顺序来遍历所有点，因此所有点到起点的距离是严格递增的，因此队首一定是最小值，所以说所有边权是1，队列相当于Dijkstra中的优先队列，队头就是一个当前最小值。
队列保持：①两段性（最多情况）；②单调性：队列中的元素距离源点的距离是单调递增的。
迷宫问题
1 |
|
武士风度的牛
1 |
|
抓住那头牛
1 |
|
多源BFS
与多源最短路不一样，多源最短路求的是没两个点之间的距离，而这里求的是每个点到各自最近起点的距离。
矩阵距离
- 对所有起点入队列然后bfs。
1 |
|
最小步数模型
即整个棋盘看做一个状态，对整个棋盘进行一些操作，成为另一个状态。难点：如何存储这个状态。（C：hash、康拓展开；C++：map、unordered_map）
魔板
1 |
|
双端队列广搜
电路维修
- 考虑迪杰斯特拉算法，边权为1和0的最短路问题，利用双端队列处理这个问题可以，遇到0插入队头，1插入队尾。
- 特殊：不用记录某一个点是否被搜到，因为0、1会使得某位置会多次入队；出队的时候才判断该元素。
1 |
|
双向广搜
一般用在最小步数模型里，因为这类问题搜索空间一般比较大，是指数级别。
实现方式：①两个方向扩展一步，每次选择当前队列中元素较少的一方进行扩展；
字串变换
A*
适合的环境：最小步数模型，即搜索空间非常大的时候；比较像dijkstra，可以看做所有估计函数都为0的算法。不能有负权回路。不能保证每一次出队的元素是最小值，只有终点出队才能保证是最小值。
估价函数：大于等于0，小于等于真实值。
必须保证有解的时候才能有，否则无解的时候效率低于BFS（队列O(1)）;
算法正确的条件：起点到当前状态的真实距离为
d(state)，从state到终点的真实距离为g(state)，估计距离为f(state),那么必须满足：f(state) <= g(state)。- 证明：假设当终点出队的时候不是最小值，此时
dist>d最优，则队列中一定存在最优解。因此发现d(u) + f(u) <= d(u) + g(u)。
1 | while(!q.empty()) |
规律：1
2
3
4
5
6
7
81、堆入队：该初始状态的估计距离 + 该初始状态；
heap.push({mDis(start), start});
2、遍历周围状态，当该状态未记录距离，或者距离小于当前真实距离：
dist[state] = step + 1;
!dist.count(state) || dist[state] > step + 1
heap.push({dist[state] + mDis(state), state});
3、目标状态第一次出队即得到最优解；
if (state == end) break;
下：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
using namespace std;
typedef pair<int, string> PIS;
char p[] = "lrud";
int ix[] = {0, 0, -1, 1}, iy[] = {-1, 1, 0, 0};
int mDis(string state)
{
int cnt = 0;
for(int i = 0; i < state.size(); i ++)
if(state[i] != 'x')
{
int t = state[i] - '1';
cnt += abs(t / 3 - i / 3) + abs(t % 3 - i % 3);
}
return cnt;
}
string AStar(string start)
{
string end = "12345678x";
unordered_map<string, pair<char, string>> pre;
unordered_map<string , int> dist;
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;
heap.push({mDis(start), start});
dist[start] = 0;
while(heap.size())
{
auto t = heap.top();
heap.pop();
string state = t.second; // state
if (state == end) break;
int step = dist[state]; //当前宽搜的真实距离
int x, y;
for(int i = 0; i < 9; i++)
if(state[i] == 'x')
{
x = i / 3, y = i % 3;
break;
}
string source = state;
for(int i = 0; i < 4; i ++)
{
int a = x + ix[i], b = y + iy[i];
if(a < 0 || a >=3 || b < 0 || b >= 3) continue;
swap(state[3 * x + y], state[3 * a + b]); //next state
if(!dist.count(state) || dist[state] > step + 1)
{
dist[state] = step + 1;
pre[state] = {p[i], source};
heap.push({dist[state] + mDis(state), state});
//heap.push({mDis(state), dist[source] + 1});
}
swap(state[3 * x + y], state[3 * a + b]); //previous state
}
}
string res;
while(end != start)
{
res += pre[end].first;
end = pre[end].second;
}
reverse(res.begin(), res.end());
return res;
}
int main()
{
string state, seq;
char c;
for(int i = 0; i < 9; i ++)
{
cin >> c;
state += c;
if (c != 'x') seq += c;
}
int cnt;
//逆序对数目
for(int i = 0; i < seq.size(); i ++)
for(int j = i + 1; j < seq.size(); j ++)
if(seq[i] > seq[j])
cnt++;
if(cnt & 1) puts("unsolvable");
else cout << AStar(state) << endl;
return 0;
}