Klotski

#include <bits/stdc++.h>
#define F first
#define S second
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
string grid[5];
 
struct state {
	pii xloc;
	pii eloc;
	pii adloc[4];
	pii filoc[4];
	
	state() {
	}
	
	state(pii xx, pii ee, pii* ad, pii* fi) : xloc(xx), eloc(ee) {
		for (int i=0;i<4;i++) {
			adloc[i]=ad[i];
			filoc[i]=fi[i];
		}
		sort(adloc,adloc+4);
		sort(filoc,filoc+4);
	}
	
	bool isSolved() {
		if (xloc.F == 3 && xloc.S == 1) return true;
		return false;
	}
	
	bool operator==(const state& ref) const {
		if (xloc!=ref.xloc) return false;
		if (eloc!=ref.eloc) return false;
		for (int i=0;i<4;i++) {
			if (adloc[i]!=ref.adloc[i]) return false;
			if (filoc[i]!=ref.filoc[i]) return false;
		}
		return true;
	}
	
	bool operator<(const state& ref) const {
		if (xloc!=ref.xloc) return xloc<ref.xloc;
		if (eloc!=ref.eloc) return eloc<ref.eloc;
		for (int i=0;i<4;i++) {
			if (adloc[i]!=ref.adloc[i]) return adloc[i]<ref.adloc[i];
			if (filoc[i]!=ref.filoc[i]) return filoc[i]<ref.filoc[i];
		}
		return false;
	}
	
	bool isFree(int i, int j) {
		if (i<0 || i>=5) return false;
		if (j<0 || j>=4) return false;
		if (xloc.F == i || xloc.F == i-1) {
			if (xloc.S == j || xloc.S == j-1) return false;
		}
		if (eloc.F == i) {
			if (eloc.S == j || eloc.S == j-1) return false;
		}
		for (int ii=0;ii<4;ii++) {
			if (adloc[ii].F == i || adloc[ii].F == i-1) {
				if (adloc[ii].S == j) return false;
			}
			if (filoc[ii].F == i && filoc[ii].S == j) return false;
		}
		return true;
	}
	
	int blockInd(int i, int j) {
		if (i<0 || i>=5) return -1;
		if (j<0 || j>=4) return -1;
		if (xloc.F == i || xloc.F == i-1) {
			if (xloc.S == j || xloc.S == j-1) return 10;
		}
		if (eloc.F == i) {
			if (eloc.S == j || eloc.S == j-1) return 5;
		}
		for (int ii=0;ii<4;ii++) {
			if (adloc[ii].F == i || adloc[ii].F == i-1) {
				if (adloc[ii].S == j) return ii+1;
			}
			if (filoc[ii].F == i && filoc[ii].S == j) return ii+6;
		}
		return -1;
	}
	
	bool checkCell(int i, int j, int block) {
//		cout<<isFree(i,j)<<" "<<blockInd(i,j)<<endl;
		if (isFree(i,j) || blockInd(i,j)==block) return true;
		return false;
	}
	
	bool canMove(int block, pii dir) {
		if (block==10) {
			if (!checkCell(xloc.F+dir.F,xloc.S+dir.S,block)) return false;
			if (!checkCell(xloc.F+dir.F+1,xloc.S+dir.S,block)) return false;
			if (!checkCell(xloc.F+dir.F,xloc.S+dir.S+1,block)) return false;
			if (!checkCell(xloc.F+dir.F+1,xloc.S+dir.S+1,block)) return false;
		} else if (block==5) {
			if (!checkCell(eloc.F+dir.F,eloc.S+dir.S,block)) return false;
			if (!checkCell(eloc.F+dir.F,eloc.S+dir.S+1,block)) return false;
		} else if (block<5) {
			if (!checkCell(adloc[block-1].F+dir.F,adloc[block-1].S+dir.S,block)) return false;
			if (!checkCell(adloc[block-1].F+dir.F+1,adloc[block-1].S+dir.S,block)) return false;
		} else {
			if (!checkCell(filoc[block-6].F+dir.F,filoc[block-6].S+dir.S,block)) return false;
		}
		return true;
	}
	
	state move(int block, pii dir) {
		state s(xloc,eloc,adloc,filoc);
		if (block==10) {
			s.xloc.F+=dir.F;
			s.xloc.S+=dir.S;
		} else if (block==5) {
			s.eloc.F+=dir.F;
			s.eloc.S+=dir.S;
		} else if (block<5) {
			s.adloc[block-1].F+=dir.F;
			s.adloc[block-1].S+=dir.S;
		} else {
			s.filoc[block-6].F+=dir.F;
			s.filoc[block-6].S+=dir.S;
		}
		sort(s.adloc,s.adloc+4);
		sort(s.filoc,s.filoc+4);
		return s;
	}
};
 
void printState(state pri) {
	for (int i=0;i<5;i++) {
		for (int j=0;j<4;j++) {
			int block=pri.blockInd(i,j);
			if (block==-1) cout<<".";
			else if (block==10) cout<<"X";
			else cout<<(char)(block+'A'-1);
		}
		cout<<endl;
	}
}
 
pair<bool,state> moveBlock(state current, int block, pii dir) {
//	printState(current);
//	cout<<block<<" "<<dir.F<<" "<<dir.S<<endl;
	if (block==-1) return {false,current};
//	cout<<block<<" "<<dir.F<<" "<<dir.S<<endl;
	if (!current.canMove(block,dir)) return {false,current};
//	cout<<block<<" "<<dir.F<<" "<<dir.S<<endl;
	return {true,current.move(block,dir)};
}
 
pii aadd[4];
pii ffii[4];
 
 
 
int bfs(state start) {
//	printState(start);
	set<state> visited;
	vector<pair<state,int>> toHandle;
	toHandle.push_back({start,0});
	visited.insert(start);
	for (unsigned int ii=0;ii<toHandle.size();ii++) {
//		cout<<ii<<endl;
		if (toHandle[ii].F.isSolved()) return toHandle[ii].S;
		state cur=toHandle[ii].F;
		for (int i=0;i<5;i++) {
			for (int j=0;j<4;j++) {
				if (cur.isFree(i,j)) {
					for (int i2=-1;i2<=1;i2++) {
						for (int j2=-1;j2<=1;j2++) {
							if (i2*j2==0 && abs(i2+j2)==1) {
								auto z = moveBlock(cur,cur.blockInd(i+i2,j+j2),{-i2,-j2});
//								cout<<"bfs "<<z.F<<" "<<visited.count(z.S)<<endl;
//								cout<<visited.size()<<endl;
								if (z.F && !visited.count(z.S)) {
									visited.insert(z.S);
									toHandle.push_back({z.S,toHandle[ii].S+1});
//									cout<<"---"<<endl;
//									printState(z.S);
//									cout<<"---"<<endl;
								}
							}
						}
					}
				}
			}
		}
//		return -1;
	}
	return -1;
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i=0;i<5;i++) cin>>grid[i];
	map<char,pii> loc;
	for (int i=0;i<5;i++) {
		for (int j=0;j<4;j++) {
			if (grid[i][j]!='.' && !loc.count(grid[i][j])) {
				loc[grid[i][j]]={i,j};
			}
		}
	}
	for (char c='A';c<='D';c++) aadd[c-'A']=loc[c];
	for (char c='F';c<='I';c++) ffii[c-'F']=loc[c];
	state starting(loc['X'],loc['E'],aadd,ffii);
	cout<<bfs(starting)<<"\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED