八数码
/*
8数码问题,给出3*3的正方形,输入初始状态以及目标状态,求出从初始状态到目标状态所需的最小步数
solution:
可以把8数码问题归结为图上的最短路进问题,图的结点就是9个格子中的滑块号,可以用BFS求解。
但是隐式图的遍历需要用一个结点查找表来判重。在这里用到了哈希表,这是竞赛中最常用的方式之一。
note:
隐式图,哈希查找表,广搜
date:
2016/5/4
*/
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxState = 1000000;
const int hashsize = 1000003;
typedef int State[9];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
State st[maxState], goal; //分别是保存每一步状态的表以及目标状态数组
int dist[maxState], head[hashsize], next[maxState];
void init_lookup_table() { memset(head, 0, sizeof(head)); }
int hash(State& s) {
int v = 0;
for(int i = 0; i < 9; i++) v = v * 10 + s[i];
return v % hashsize;
}
bool insertTable(int s) {
int h = hash(st[s]);
int u = head[h];
while(u) {
if(memcmp(st[u], st[s], sizeof(st[s])) == 0) return false;
u = next[u];
}
next[s] = head[h];
head[h] = s;
return true;
}
int bfs() {
init_lookup_table();
int before = 1, rear = 2; //st从1下标开始
while(before < rear) {
State& s = st[before];
if(memcmp(goal, s, sizeof(s)) == 0) return before; //如果已经是目标状态则立即返回before
int z;
for(z = 0; z < 9; z++) if(s[z] == 0) break;
int x = z / 3, y = z % 3; //找到0即空格的位置
for(int d = 0; d < 4; d++) { //依次向周围4个方向移动
int newx = x + dx[d];
int newy = y + dy[d];
int newz = newx * 3 + newy;
if(newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
State& t = st[rear];
memcpy(&t, &s, sizeof(s));
t[newz] = s[z]; //将新的空格位置赋值0
t[z] = s[newz]; //将原来的空格填上移到空格的数字
dist[rear] = dist[before] + 1;
if(insertTable(rear)) rear++;
}
}
before++;
}
return 0;
}
int main()
{
freopen("input.txt", "r", stdin);
int kase;
scanf("%d", &kase);
while(kase--) {
for(int i = 0; i < 9; i++) scanf("%d", &st[1][i]);
for(int i = 0; i < 9; i++) scanf("%d", &goal[i]); //输入初始状态以及目标状态
int ans = bfs(); //广搜遍历隐式图,给出答案
if(ans > 0) printf("%d\n", dist[ans]);
else printf("-1\n");
}
return 0;
}
---------------------
本文来自 林伏案 的**** 博客 ,全文地址请点击:https://blog.****.net/qq_29169749/article/details/51419840?utm_source=copy
其中遇到的疑问
一.z/3
结合下图
发现坐标身上的数字是从0横向依次递增的,x每增1,相当于多一行,剩下的余值,可用小于3的y值代替,这样就形成的一个表达式z=x*3+y,是不是就是除法的还原式,这样把z分解为x和y就能控制格子移动了
二.State& t = st[rear]; memcpy(&t, &s, sizeof(s));
的含义如下图,假如此时首指针指向st[5],代码的含义就是把首指针的内容复制给尾指针st[9],(尾指针一直指向首个不全为0的数组位置)
三
t[newz] = s[z]; //
t[z] = s[newz];
含义是把空白块0的值和刚找到的满足条件的newz的位置的值交换,既达到移动效果
运行时的结果显示如下
四
if (try_to_insert(rear)) rear++;
去重,也即是防止重复移动,如上如把白色空格移动到1位置,下次白色空格再向1移动,即使移动条件满足,也不会移动,既尾指针没增加一,没做移动效果
原理就是vis数组会保存每次合法移动后的值,如下图
如果有重复会直接返回0,反之存入vis返回1,这里书上说了还有好几种方法,比较好的是hash,但在规模不大情况下,这个方法页不错,
五
总体思想就是BFS,可以参考https://blog.****.net/u011221820/article/details/80476230
非hash版代码如下
#include"stdafx.h"
// 八数码,使用STL集合(最好写)
// Rujia Liu
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
typedef int State[9];
const int MAXSTATE = 1000000;
State st[MAXSTATE], goal;
int dist[MAXSTATE];
set<int> vis;
void init_lookup_table() { vis.clear(); }
int try_to_insert(int s) {
int v = 0;
for (int i = 0; i < 9; i++)
v = v * 10 + st[s][i];
if (vis.count(v)) return 0;
vis.insert(v);
return 1;
}
const int dx[] = { -1, 1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
int bfs() {
init_lookup_table();
int front = 1, rear = 2;
while (front < rear) {
State& s = st[front];
if (memcmp(goal, s, sizeof(s)) == 0) return front;
int z;
for (z = 0; z < 9; z++) if (!s[z]) break;
int x = z / 3, y = z % 3;
for (int d = 0; d < 4; d++) {
int newx = x + dx[d];
int newy = y + dy[d];
int newz = newx * 3 + newy;
if (newx >= 0 && newx < 3 && newy >= 0 && newy < 3) {
State& t = st[rear];
memcpy(&t, &s, sizeof(s));
t[newz] = s[z]; //
t[z] = s[newz];
dist[rear] = dist[front] + 1;
if (try_to_insert(rear)) rear++;
}
}
front++;
}
return 0;
}
int main() {
for (int i = 0; i < 9; i++)
scanf("%d", &st[1][i]);
for (int i = 0; i < 9; i++)
scanf("%d", &goal[i]);
int ans = bfs();
if (ans > 0) printf("%d\n", dist[ans]);
else printf("-1\n");
return 0;
}