CLOCK - Chỉnh đồng hồ
Tác giả: skyvn97
Ngôn ngữ: C++
#include<stdio.h>
#include<queue>
using namespace std;
queue<int> q;
int mv[9][9]={{1,1,0,1,1,0,0,0,0},{1,1,1,0,0,0,0,0,0},{0,1,1,0,1,1,0,0,0},{1,0,0,1,0,0,1,0,0},{0,1,0,1,1,1,0,1,0},{0,0,1,0,0,1,0,0,1},{0,0,0,1,1,0,1,1,0},{0,0,0,0,0,0,1,1,1},{0,0,0,0,1,1,0,1,1}};
int f;
int c[262144];
int l[262144];
void init(void) {
int i,j;
int a[3][3];
char s[3];
for (i=0;i<3;i=i+1) {
scanf("%s",s);
for (j=0;j<3;j=j+1) a[i][j]=s[j]-48;
}
int tmp=1;
f=0;
for (i=2;i>=0;i=i-1)
for (j=2;j>=0;j=j-1) {
f=f+a[i][j]*tmp;
tmp=tmp*4;
}
}
int move(int s,int p) {
int i,v;
for (i=0;i<9;i=i+1)
if (mv[p][i]==1) {
v=((s|(1<<(17-2*i)))==s)*2+((s|(1<<(16-2*i)))==s);
if (v<3) s=s+(1<<(16-2*i));
else s=s-(3<<(16-2*i));
}
return (s);
}
void BFS(void) {
q.push(f);
c[f]=1;
l[f]=0;
int x,y,i;
while (!q.empty()) {
x=q.front(); q.pop();
if (x==0) {
printf("%d",l[x]);
return;
}
for (i=0;i<9;i=i+1) {
y=move(x,i);
if (c[y]==0) {
c[y]=1;
l[y]=l[x]+1;
q.push(y);
}
}
}
printf("-1");
}
int main(void) {
init();
BFS();
return 0;
}