4 solutions
-
2
包对的（无注释）
#include<bits/stdc++.h> using namespace std; map<string,int> dist; string move0(string s) { string str=s; for(int i=0;i<4;i++) { swap(str[i],str[7-i]); } return str; } string move1(string s) { string str=s; char ch; ch=str[3]; for(int i=2;i>=0;i--) { str[i+1]=str[i]; } str[0]=ch; ch=str[4]; for(int i=5;i<=7;i++) { str[i-1]=str[i]; } str[7]=ch; return str; } string move2(string s) { string str=s; char ch=str[1]; str[1]=str[6]; str[6]=str[5]; str[5]=str[2]; str[2]=ch; return str; } int bfs(string start,string end) { if(start==end) { return 0; } queue<string> q; q.push(start); dist[start]=0; while(q.size()) { string m[3]; string str=q.front(); if(str==end) { return dist[end]; } q.pop(); m[0]=move0(str); m[1]=move1(str); m[2]=move2(str); for(int i=0;i<3;i++) { if(!dist.count(m[i])) { dist[m[i]]=dist[str]+1; q.push(m[i]); } } } return -1; } int main() { string start="12345678",end; for(int i=0;i<8;i++) { char x; cin>>x; end+=x; } int step=bfs(start,end); cout<<step; return 0; } -
2
包对的（有注释）
#include<bits/stdc++.h> using namespace std; map<string,int> dist; string move0(string s) //A操作 { string str=s; for(int i=0;i<4;i++) //前后交换 { swap(str[i],str[7-i]); } return str; } string move1(string s) //B操作 { string str=s; char ch; ch=str[3]; //第一列移动 for(int i=2;i>=0;i--) { str[i+1]=str[i]; } str[0]=ch; ch=str[4]; //第二列移动 for(int i=5;i<=7;i++) { str[i-1]=str[i]; } str[7]=ch; return str; } string move2(string s) { string str=s; char ch=str[1]; //顺时针旋转 str[1]=str[6]; str[6]=str[5]; str[5]=str[2]; str[2]=ch; return str; } int bfs(string start,string end) //宽搜 { if(start==end) { return 0; } queue<string> q; q.push(start); dist[start]=0; while(q.size()) { string m[3]; string str=q.front(); if(str==end) //找到终点 { return dist[end]; } q.pop(); m[0]=move0(str); m[1]=move1(str); m[2]=move2(str); for(int i=0;i<3;i++) { if(!dist.count(m[i])) //当前这个方案还没有出现过 { dist[m[i]]=dist[str]+1; q.push(m[i]); } } } return -1; //找不到 } int main() { string start="12345678",end; for(int i=0;i<8;i++) { char x; cin>>x; end+=x; } int step=bfs(start,end); cout<<step; return 0; } -
1
#include<bits/stdc++.h> using namespace std; map<string,int> dist; string move0(string s) { string str=s; for(int i=0;i<4;i++) { swap(str[i],str[7-i]); } return str; } string move1(string s) { string str=s; char ch; ch=str[3]; for(int i=2;i>=0;i--) { str[i+1]=str[i]; } str[0]=ch; ch=str[4]; for(int i=5;i<=7;i++) { str[i-1]=str[i]; } str[7]=ch; return str; } string move2(string s) { string str=s; char ch=str[1]; str[1]=str[6]; str[6]=str[5]; str[5]=str[2]; str[2]=ch; return str; } int bfs(string start,string end) { if(start==end) { return 0; } queue<string> q; q.push(start); dist[start]=0; while(q.size()) { string m[3]; string str=q.front(); if(str==end) { return dist[end]; } q.pop(); m[0]=move0(str); m[1]=move1(str); m[2]=move2(str); for(int i=0;i<3;i++) { if(!dist.count(m[i])) { dist[m[i]]=dist[str]+1; q.push(m[i]); } } } return -1; } int main() { string start="12345678",end; for(int i=0;i<8;i++) { char x; cin>>x; end+=x; } int step=bfs(start,end); cout<<step; return 0; } -
1
#include<bits/stdc++.h> using namespace std; map<string,int> dist; string move0(string s) //A操作 { string str=s; for(int i=0;i<4;i++) //前后交换 swap(str[i],str[7-i]); return str; } string move1(string s) //B操作 { string str=s; char ch; ch=str[3]; //第一列移动 for(int i=2;i>=0;i--) str[i+1]=str[i]; str[0]=ch; ch=str[4]; //第二列移动 for(int i=5;i<=7;i++) str[i-1]=str[i]; str[7]=ch; return str; } string move2(string s) { string str=s; char ch=str[1]; //顺时针旋转 str[1]=str[6]; str[6]=str[5]; str[5]=str[2]; str[2]=ch; return str; } int bfs(string start,string end) //宽搜 { if(start==end) return 0; queue<string> q; q.push(start); dist[start]=0; while(q.size()) { string m[3]; string str=q.front(); if(str==end) //找到终点 { return dist[end]; } q.pop(); m[0]=move0(str); m[1]=move1(str); m[2]=move2(str); for(int i=0;i<3;i++) { if(!dist.count(m[i])) //当前这个方案还没有出现过 { dist[m[i]]=dist[str]+1; q.push(m[i]); } } } return -1; //找不到 } int main() { string start="12345678",end; for(int i=0;i<8;i++) { char x; cin>>x; end+=x; } int step=bfs(start,end); cout<<step; return 0; }
lizi12
LV 6
@ 2024-7-31 15:14:20
- 1