Acwing 1107 魔闆

題目傳送門

分析：

我們可以把每一種棋盤狀态看作一個結點，因為一共就8位數，是以結點數是有限的。也就是說我們可以用這些結點建構一個無向圖。

又因為每次轉換的“花費”是相同的，即花一次轉換機會

是以圖上的邊權也相等

而題目的問題就可以轉化為求邊權相等的圖上兩個點的最短距離

那麼就很明顯是bfs了

代碼：

#include<bits/stdc++.h>  
using namespace std;

#define fi first
#define se second     

string st = "12345678", dt = "";

//和起點的距離
map<string, int>dis;

//手寫隊列
string q[N * N];

//記錄路徑 -> 從哪個狀态來，以什麼方式來的
map<string, pair<string, char> >pre;

//三種操作
string op(string now, char c){
	string ans = "";
	if(c == 'A'){
		for(int i = 7; i >= 4; i--) ans += now[i];
		for(int i = 3; i >= 0; i--) ans += now[i];
	}
	else if(c == 'B'){
		ans += now[3];
		for(int i = 0; i < 3; i++) ans += now[i];
		for(int i = 5; i <= 7; i++) ans += now[i];
		ans += now[4];
	}
	else{
		int gs[] = {0, 6, 1, 3, 4, 2, 5, 7};
		for(int i = 0; i < 8; i++) ans += now[gs[i]];
	} 
	return ans;
}


//bfs模闆
int bfs(){
	int hh = 0, tt = -1;
	
	q[++tt] = st;
	dis[st] = 0;

	while(hh <= tt){
		auto tp = q[hh++];
		if(tp == dt) return dis[dt];

		string temp = op(tp, 'A');
		if(!dis.count(temp)){
			dis[temp] = dis[tp] + 1;
			q[++tt] = temp;
			pre[temp] = {tp, 'A'};
		} 
		
		temp = op(tp, 'B');
		if(!dis.count(temp)){
			dis[temp] = dis[tp] + 1;
			q[++tt] = temp;
			pre[temp] = {tp, 'B'};
		}
		
		temp = op(tp, 'C');
		if(!dis.count(temp)){
			dis[temp] = dis[tp] + 1;
			q[++tt] = temp;
			pre[temp] = {tp, 'C'};
		}
	}
}

int main(){
	for(int i = 0; i < 8; i++){
		int x;
		scanf("%d", &x);
		dt += x + '0';
	} 
	
	int t = bfs();
	cout << t << endl;
	
	string path = "", now = dt;

	while(now != st){
		path += pre[now].se;
		now = pre[now].fi;
	}
    
	reverse(path.begin(), path.end());
		
	if(t) cout << path << endl;
	
	return 0;
}
           

如果覺得不錯，不妨給個👍再走呗~