【codevs1004】四子连棋 状压bfs

题目大意:给定一个大小为 4*4 的棋盘,分别有 7 个黑子、7 个白子和 2 个空位构成,求出至少需要移动多少步,才能使得四个相同的棋子共线。

题解:显然每一种棋盘的局面都是一个状态,因此需要采用状态压缩的搜索。总共的局面最多有4e7种,并且所给的内存足够开下哈希表。

需要注意的是,数据中有很多不是对称的情况,因此需要分别考虑先移动白子和黑子的情况,再取最小值,得到答案。

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn=5e7;
const int inf=0x3f3f3f3f;
const int dx[]={0,0,-1,1};
const int dy[]={1,-1,0,0};
//b->1 w->0 o->2
char s[10];
int state[5][5],mp[2][maxn],ans=inf,st;
bool col[maxn]; //b->1 w->0 int get_hash(int a[5][5]){
int val=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
val=val*3+a[i][j];
return val;
} void get_state(int val){
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
state[i][j]=val%3,val/=3;
} void read_and_parse(){
for(int i=1;i<=4;i++){
scanf("%s",s+1);
for(int j=1;j<=4;j++){
if(s[j]=='B')state[i][j]=1;
if(s[j]=='W')state[i][j]=0;
if(s[j]=='O')state[i][j]=2;
}
}
st=get_hash(state);
} bool right(int x,int y,int cor){
if(x<1||y<1||x>4||y>4||state[x][y]!=cor)return 0;
return 1;
}
bool check(int a[5][5]){
for(int i=1;i<=4;i++){
if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4])return 1;
if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i])return 1;
}
if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4])return 1;
if(a[1][4]==a[2][3]&&a[2][3]==a[3][2]&&a[3][2]==a[4][1])return 1;
return 0;
} void solve(int cor){
queue<int> q;
q.push(st),mp[cor][st]=1,col[st]=cor;
while(q.size()){
int u=q.front();q.pop();
get_state(u);
if(check(state)){ans=min(ans,mp[cor][u]-1);return;}
for(int i=1;i<=4;i++)for(int j=1;j<=4;j++)if(state[i][j]==2){
for(int k=0;k<4;k++){
int nx=i+dx[k],ny=j+dy[k];
if(!right(nx,ny,col[u]))continue;
swap(state[i][j],state[nx][ny]);
int v=get_hash(state);
if(!mp[cor][v])mp[cor][v]=mp[cor][u]+1,col[v]=col[u]^1,q.push(v);
swap(state[i][j],state[nx][ny]);
}
}
}
} int main(){
read_and_parse();
solve(1);solve(0);
printf("%d\n",ans);
return 0;
}
上一篇:Pgsql之查询一段时间内的所有日期


下一篇:pgsql的动态sql之单引号的处理