90 TLE on #10
查看原帖
90 TLE on #10
477821
toolong114514楼主2023/5/16 20:40
#include<iostream>
#include<cstring>
#include<string>
#include<queue>
#include<map>
#include<set>
using namespace std;
struct xs{
	string x;
	int s;
};
set<string> vst;
//map<string,bool> vst;
int t[5]={-1,1,4,-4};//左右下上 
xs q[1000000];
string w,st;
int head,tail;
void bfs(){
	while(head<=tail){
		xs now=q[head];
		if(now.x==w){
			cout<<now.s;
			return;
		}
		int len=now.x.size();
		for(int i=0;i<len;i++){
			for(int j=0;j<4;j++){
				if(((i+1)%4)==1&&(j==0)) continue;
				if(((i+1)%4)==0&&(j==1)) continue;
				if(i<4&&(j==3)) continue;
				if(i>12&&(j==2)) continue;
				xs nxt={now.x,now.s+1};
				if(nxt.x[i]==nxt.x[i+t[j]]) continue;
				char tmp=nxt.x[i];
				nxt.x[i]=nxt.x[i+t[j]];
				nxt.x[i+t[j]]=tmp;
				if(vst.find(nxt.x)==vst.end()){
					vst.insert(nxt.x);
					q[tail+1]=nxt;
					tail++;
				}
			}
		}
		head++;
	}
	cout<<-1;
	return;
}
int main(){
	char a[100][100],b[100][100];
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>a[i][j];
			st.push_back(a[i][j]);
		}
	}
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			cin>>b[i][j];
			w.push_back(b[i][j]);
		}
	}
//	for(int i=1;i<=4;i++){
//		for(int j=1;j<=4;j++){
//			
//		}
//	}
//	for(int i=1;i<=4;i++){
//		for(int j=1;j<=4;j++){
//			
//		}
//	}
	vst.insert(st);
	q[tail]={st,0};
	bfs();
	return 0;
}
2023/5/16 20:40
加载中...