洛谷 P1379. 八数码难题
原题链接
简单
作者:
y总的小迷弟
,
2023-08-08 21:38:04
,
所有人可见
,
阅读 72
//简单宽搜,细心点即可
#include<bits/stdc++.h>
using namespace std;
struct xyh
{
string f;
int s;
int step;
};
string a;
string target;
queue<xyh> q;
map<string, int> m;
int dx[5] = {0, 1, 0, -1};
int dy[5] = {1, 0, -1, 0};
int bfs()
{
int i, cnt = 0;
for(i = 0;i < a.size();i++)
if(a[i] == '0')
break;
q.push({a, i, 0});
m[a] = 1;
while(!q.empty())
{
cnt++;
xyh t = q.front();
q.pop();
string b = t.f;
int ver = t.s;
int step = t.step;
int x = 0, y = 0;string c;
if(b == target)
return step;
if((ver + 1) % 3 == 0)
{
x = (ver + 1) / 3;
y = 3;
}
else
{
x = (ver + 1) / 3 + 1;
y = (ver + 1) % 3;
}
for(int i = 0;i < 4;i++)
{
c = b;
int nx = x + dx[i];
int ny = y + dy[i];
if(nx >= 1 && nx <= 3
&& ny >= 1 && ny <= 3)
{
int ve = (nx - 1) * 3 + ny - 1;
swap(c[ver], c[ve]);
if(m[c] == 0)
{
m[c] = 1;
q.push({c, ve, step + 1});
}
}
}
}
}
int main()
{
cin >> a;
target = "123804765";
int ans = bfs();
cout << ans << endl;
return 0;
}
《xyh》