位运算+bfs
本来用iterator来做队列的指针,但是莫名其妙的错误..
于是用了int来做指针..安心啊.
#include <iostream>
#include <vector>
using namespace std;
bool hash[65536];
vector<int> answer;
int fstate[16]=
{
0xF888,0xF444,0xF222,0xF111,
0x8F88,0x4F44,0x2F22,0x1F11,
0x88F8,0x44F4,0x22F2,0x11F1,
0x888F,0x444F,0x222F,0x111F};
struct state
{
int value;
int change;
int father;
};
vector<state> list;
void jude(int v)
{
if (v==0)
{
int iter=list.size()-1;
while(iter!=0)
{
answer.push_back(list.at(iter).change);
iter=list.at(iter).father;
}
cout<<answer.size()<<endl;
for (int i=answer.size()-1;i>=0;--i)
{
cout<<answer.at(i)/4+1<<" "<<answer.at(i)%4+1<<endl;
}
int cc;cin>>cc;
exit(0);
}
}
void init()
{
int x=0,u=1;
for (int i=0;i<4;i++)
for (int j=0;j<4;j++)
{
char ch;
cin>>ch;
int k;
switch(ch)
{
case '-':k=0;break;
case '+':k=1;break;
default:break;
}
x=x*2+k;
}
hash[x]=true;
state st;
st.value=x;
st.change=-1;
st.father=0;
list.push_back(st);
jude(x);
}
void bfs()
{
vector<state>::iterator iter=list.begin();
int left=0;
while (left<list.size())
{
state st=list.at(left);
int value=st.value;
for (int i=0;i<16;i++)
{
int n=fstate[i]^value;
if (hash[n]) continue;
state sta;
sta.value=n;
sta.father=left;
sta.change=i;
hash[n]=true;
list.push_back(sta);
jude(n);
}
left++;
}
}
int main()
{
init();
bfs();
return 0;
}