第一次使用位运算

 

其中两个重要的函数,可以加入代码库

 

// get dig from t, right xth
int getDig(int t, int x)
{
return t>>(x-1)&1;
}
void changeDig(int& t, int x)
{
t
=t^(1<<(x-1));
}

 

用BFS搜,加状态压缩,最多2^16个状态

 

#include <iostream>
#define maxn 65540
#define F(i,a,b) for (int i=a;i<=b;i++)
#include
<vector>
using namespace std;
// get dig from t, right xth
int getDig(int t, int x)
{
return t>>(x-1)&1;
}
void changeDig(int& t, int x)
{
t
=t^(1<<(x-1));
}
int Q[maxn], mk[maxn], f[maxn], l[maxn], r[maxn], now, last, start;
void bfs()
{
//init
now=0, last=0;
Q[
++last]=start;
mk[start]
=true;
while (true)
{
int s=Q[++now];
int temp=s;
F(i,
1,4)
{
F(j,
1,4)
{
int temp=s;
//ith row
F(k,0,3)
changeDig(temp,
20-4*i-k);
F(k,
0,3)
changeDig(temp,
5-j+k*4);
changeDig(temp,
17-4*(i-1)-j );
if (!mk[temp])
{
Q[
++last]=temp;
mk[temp]
=true;
f[last]
=now;
l[last]
=i;
r[last]
=j;
if (temp==( (1<<16)-1) )
{
vector
<int> v;
int k=last, total=0;
while (f[k]!=0)
{
v.push_back(k);
k
=f[k];
total
++;
}
cout
<< total << endl;
vector
<int>::iterator it=v.end()-1;
cout
<< l[*it] << " " << r[*it] << endl;
while (it!=v.begin() )
{
it
--;
cout
<< l[*it] << " " << r[*it] << endl;
}
return;
}
}
}
}
}
}
int main()
{
char ch;
start
=0;
for (int i=1;i<=16;i++)
{
//in
cin >> ch;
if (i!=1)
start
<<=1;
if (ch=='-')
start
++;
}
bfs();
return 0;
}