八数码题目
  • 板块灌水区
  • 楼主CSDN_dalao
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/6/3 14:58
  • 上次更新2023/10/23 14:00:20
查看原帖
八数码题目
707380
CSDN_dalao楼主2023/6/3 14:58

pos*nx!=6有什么用?

#include<bits/stdc++.h>

using namespace std;

string ss;

string t="123804765";

int d[4]={-1,1,-3,3};

struct str{
	string s;
	int step;
};

map<string,int>used;

int bfs(){

	queue<str>q;
    
	q.push({ss,0});
    
	used[ss]=1;
    
	while(!q.empty()){
		str f=q.front();
		q.pop();
		if(f.s==t)return f.step;
		int pos=f.s.find("0",0);
		for(int i=0;i<4;i++){
			int nx=pos+d[i];
							if(nx>=0&&nx<9&&pos*nx!=6&&pos*nx!=30){
				string tmp=f.s;
									swap(tmp[pos],tmp[nx]);
				if(!used[tmp]){
								q.push({tmp,f.step+1});
					used[tmp]=1;
				}
			}
		}
	} 
}
int main(){

	cin>>ss;
    
	cout<<bfs();
    
	return 0;
}
2023/6/3 14:58
加载中...