AcWing 000. 八数码
原题链接
简单
作者:
CqAq
,
2024-04-10 16:34:20
,
所有人可见
,
阅读 7
算法1
C++ 代码
//////////////八数码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string final;
string ori = "ABCDE*";
int n;
int d[][2] = {1,0,-1,0,0,1,0,-1};
bool inmap(int x, int y){
return (x >= 0 && x < 2 && y >= 0 && y < 3);
}
int bfs(){
unordered_map<string,int> UU;
queue<string> q;
q.push(ori); UU[ori] = 0;
while(!q.empty()){
auto p = q.front(); q.pop();
if(p == final) return 1;
for(int i = 0; i < 4; ++ i){
int k = p.find('*');
int x = k / 3 + d[i][0], y = k % 3 + d[i][1]; //这个3,和列数有关
if(inmap(x,y)){
swap(p[x*3+y], p[k]);
if(!UU[p]){
UU[p] = 1;
q.push(p);
}
swap(p[x*3+y], p[k]);///恢复原样
}
}
}
return 0;
}
int main(){
//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++ i){
cin >> final;
cout << bfs() << '\n';
//cout << 1 << '\n';
}
return 0;
}