Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
位运算水过~#include <cstdlib> #include <cstdio> #include <iostream> #include <queue> #include <cstring> using namespace std; char map[5][5]; bool vis[65540],flag; struct NOTE { int num,rod,last; }tp; void read() { for(int i=0;i<=3;i++) scanf("%s",&map[i]); } void pretreat() { tp.rod=0;tp.last=0;tp.num=0; for(int i=0;i<=3;i++) for(int j=0;j<=3;j++) if(map[i][j]=='w') tp.num+=1<<(4*i+j); vis[tp.num]=1; //cout<<tp.num<<endl; } void bfs() { queue<NOTE> q; q.push(tp); while(!q.empty()) { NOTE tmp=q.front(); q.pop(); int nb=tmp.num,lt=tmp.last,rd=tmp.rod; if(rd>=16) return; for(int i=lt+1;i<=16;i++) { int dk=nb; dk=dk^(1<<(i-1)); if(((i-1)%4)!=0) dk=dk^(1<<(i-2)); if(((i+1)%4)!=1) dk=dk^(1<<(i)); if(i-4>0) dk=dk^(1<<(i-5)); if(i+4<=16) dk=dk^(1<<(i+3)); //cout<<dk<<endl;system("pause"); if(dk==65535||dk==0) { printf("%d",rd+1); flag=1; return; } if(vis[dk]!=1) { vis[dk]=1; NOTE pq; pq.num=dk;pq.last=i;pq.rod=rd+1; q.push(pq); } } } } int main() { read(); pretreat(); if(tp.num==65535||tp.num==0) { printf("0"); return 0; } bfs(); if(flag!=1) printf("Impossible"); system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator