首页 > 代码库 > bfs-poj1753
bfs-poj1753
http://poj.org/problem?id=1753
简单的一个bfs,棋盘状态用一个无符号十六位short存储,每一个0或1代表白与黑,改变用位运算,change数组中存储了十六种改变.
棋盘状态=0或65535即每位都是0或每位都是1时结束
#include <cstdio> #include <queue> #include <cstring> #include <iostream> using namespace std; short flag[65536]={0}; unsigned short change[16]={ 51200, 58368, 29184, 12544, 35968, 20032, 10016, 4880, 2248, 1252, 626, 305, 140, 78, 39, 19 }; queue<unsigned short> q; queue<unsigned short> cq; unsigned short bfs(){ unsigned short p=q.front(),cp=cq.front(); q.pop(); cq.pop(); if(flag[p]){ return 65535; } flag[p]=1; if(p==0 || p==65535){ return cp; }else{ cp++; for(int i=0;i<16;i++){ q.push(p^change[i]); cq.push(cp); } } return 65535; } int main(){ unsigned short head=0; char tmp; for(int i=0;i<16;i++){ cin>>tmp; if(tmp==‘b‘){ head=head|(1<<i); } } q.push(head); cq.push(0); int k=bfs(); while(k==65535 && q.size()){ k=bfs(); } if(k!=65535){ printf("%d\n",k); }else{ printf("Impossible\n"); } return 0; }
bfs-poj1753
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。