首页 > 代码库 > 黑白棋游戏（或是叫再破难关）——稍微用了下状态压缩的bfs
黑白棋游戏（或是叫再破难关）——稍微用了下状态压缩的bfs
洛谷和CodeVS 上叫做黑白棋游戏，要求输出路径。CodeVS 上没有spj，洛谷上有但是我的输出总是直接报错。最后找到了Vijos 上的再破难关，一样的题，只是不需要输出路径，交了就对了。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 using namespace std; 8 const int xdr[]={4,-4,1,-1},ax[]={-1,1,0,0},ay[]={0,0,-1,1};//上 下 左 右 9 struct node{int num,s;};10 11 int sx,tx,mark=15,res,code[8][8],cnt,fth[2<<18],mv[2<<18];12 bool vis[2<<18];13 14 void bfs(){15 queue<node> q;16 q.push((node){sx,0});17 vis[sx]=true;18 fth[sx]=0;19 20 while(!q.empty()){21 int x=q.front().num,s=q.front().s;22 if(x==tx){23 cout<<s<<endl;24 exit(0);25 }26 q.pop();27 28 29 for(int i=1;i<=4;i++)30 for(int j=1;j<=4;j++)31 if(x&code[i][j])32 for(int k=0;k<4;k++){33 if((k==0&&i==1)||(k==1&&i==4)||34 (k==2&&j==1)||(k==3&&j==4)||35 (x&code[i+ax[k]][j+ay[k]]))36 continue;37 38 int nx=x+code[i+ax[k]][j+ay[k]]-code[i][j];39 if(vis[nx])continue;40 vis[nx]=true;41 42 mv[nx]=i*1000+j*100+(i+ax[k])*10+j+ay[k];43 44 fth[nx]=x;45 q.push((node){nx,s+1});46 47 }48 }49 }50 51 int main(){52 for(int i=1;i<=4;i++)53 for(int j=1;j<=4;j++)54 code[i][j]=1<<mark--;55 56 mark=15;57 for(int i=1;i<=4;i++){58 for(int j=1;j<=4;j++){59 char c=getchar();60 sx+=(1<<mark)*(c==‘1‘);61 mark--;62 }63 getchar();64 }65 getchar();66 mark=15;67 for(int i=1;i<=4;i++){68 for(int j=1;j<=4;j++){69 char c=getchar();70 tx+=(1<<mark)*(c==‘1‘);71 mark--;72 }73 getchar();74 }75 mark=0;76 bfs();77 return 0;78 }
Vijos 63ms
黑白棋游戏（或是叫再破难关）——稍微用了下状态压缩的bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。