双端队列
用单队列实现双端队列时需要注意标记数组是不一样的。我们让我们想要的第一个队列用\(1\)来标记，第二个用\(2\)来标记，那么当他们碰面的时候也就是\(1+2=3\)的时候就是我们想要的答案。
-
双端队列开数组来记录权值。
-
标记要标记传标记\(vis[now] = vis[cur];\)。
-
双端队列对走过点的判断条件是\(vis\)相同。
思路
将\(3\times 3\)数组化为一位数组来储存，移动的时候再转换为\(3\times 3\)数组。
需要特判还没入队就相等的情况。
交换后记得交换回来。
如果这个点和\(cur\)的\(vis\)相同记得换回地图(\(swap\))，因为这个点已经走过了。
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define DOF 0x7f7f7f7f
#define endl '\n'
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(case, x) cout << case << " : " << x << endl
#define open freopen("ii.txt", "r", stdin)
#define close freopen("oo.txt", "w", stdout)
#define IO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define pb push_back
using namespace std;
#define int long long
#define lson rt << 1
#define rson rt << 1 | 1
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> PII;
const int maxn = 1e6 + 10;
int str;
int dir[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int mt[5][5];
map<int,int>dis;
map<int,int>vis;
void bfs() {
queue<int>q;
int flag = 123804765;
if(str==flag){
cout<<0<<endl;
return ;
}
q.push(str);
q.push(flag);
vis[str] = 1;
vis[flag] = 2;dis[str]=0,dis[flag]=0;
while(!q.empty()) {
int now = q.front();
int cur = now;
q.pop();
int sx=1, sy=1;
for(int i = 3; i >= 1; --i) {
for(int j = 3; j >= 1; --j) {
mt[i][j] = now % 10;
now /= 10;
if(mt[i][j]==0)sx = i, sy = j;
}
}
for(int i = 0; i < 4; ++i) {
int xx = sx + dir[i][0], yy = sy + dir[i][1];
if(xx < 1 || xx > 3 || yy < 1 || yy > 3)continue;
swap(mt[sx][sy], mt[xx][yy]);
now = 0;
for(int j = 1; j <= 3; ++j) {
for(int i = 1; i <= 3; ++i) {
now = now * 10 + mt[j][i];
}
}
if(vis[cur] == vis[now]) {
swap(mt[sx][sy], mt[xx][yy]);
continue;
}
if(vis[cur] + vis[now] == 3) {
cout << dis[cur]+dis[now]+1 << endl;
return ;
}
dis[now]=dis[cur]+1;
vis[now] = vis[cur];
q.push(now);
swap(mt[sx][sy],mt[xx][yy]);
}
}
}
signed main() {
cin >> str;
bfs();
}