巢穴

about:blank

P2965

   位运算+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;
}

posted on 2009-10-01 16:13 Vincent 阅读(124) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理