九宫格拼图问题就是在3*3的格子上摆放8张拼图,空出一个格子,玩家要借助这个空格上下左右移动完成拼图,求完成拼图最少要移动多少次
题目:ALDS1_13_B
其实这个问题可以看成是在移动空格,并且记录下经过的所有状态。
我们把九宫格按照下面的方式进行编号:
那么就可以用一个一维数组来存储这些格子。
设一维数组下标为a,对于x、y坐标,有如下关系:
x=a/3, y=a%3
然后就可以应用bfs来求解了。代码如下:
#include <bits/stdc++.h>
using namespace std;
#define N 3
#define N2 9
const int dx[] = {0, 0, -1, 1}; //分别对应上下左右移动
const int dy[] = {1, -1, 0, 0};
const string pth[] = {"u", "d", "l", "r"};
struct node
{
string path = "";
int f[N2];
int space; //空格所在位置
bool operator<(const node &p)const
{
for(int i=0;i<N2;++i)
{
if(f[i]==p.f[i])
continue;
return f[i]<p.f[i];
}
return false;
}
};
bool is_target(node nd)
{
for (int i = 0; i < 9; ++i)
{
if (nd.f[i] != i + 1)
return false;
}
return true;
}
string bfs(node st)
{
queue<node> Q;
map<node, bool> mp;
st.path = "";
Q.push(st);
mp[st] = true;
node u, v;
while (!Q.empty())
{
u = Q.front();
Q.pop();
if (is_target(u))
return u.path;
int sx = u.space / N;
int sy = u.space % N;
for (int i = 0; i < 4; ++i)
{
int tx = sx + dx[i];
int ty = sy + dy[i];
if (tx >= N || tx < 0 || ty >= N || ty < 0)
continue;
v = u;
v.path += pth[i];
swap(v.f[u.space], v.f[N * tx + ty]);
v.space = N * tx + ty;
if(!mp[v])
{
//确保没有存在过这条路径
mp[v] = true;
Q.push(v);
}
}
}
return "cannot_solve";
}
int main()
{
node st;
for (int i = 0; i < N2; ++i)
{
cin >> st.f[i];
if (st.f[i] == 0)
{
st.space = i;
st.f[i] = N2;
}
}
string ans = bfs(st);
if(ans!="cannot_solve")
cout<<ans.length()<<endl;
}
转载请注明来源:https://www.longjin666.top/?p=1069
欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~