「CODEVS1004」四子连棋
题目描述 Description
在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。
● ○ ● ○ ● ○ ● ● ○ ● ○ ○ ● ○
输入描述 Input Description
输出描述 Output Description
用最少的步数移动到目标棋局的步数。
样例输入 Sample Input
BWBO
WBWB
BWBW
WBWO
样例输出 Sample Output
5
题解
这显然是一道搜索相关的题目，每次找到空白的格子，将其与四周的棋子进行交换
这类求最小步数的题目往往迭代深搜可以秒杀
如果使用广度搜索，由于总局面数达到4 * 10^7，我们需要对局面进行判重，剪除重复搜索的分枝
这就需要用到哈希表，将局面看做16位的三进制数，转换十进制后取模作为key
据说迭代深搜可以秒杀
本题代码不考虑哈希表冲突的情况，不过由于最少步数的情况较多，得到错解的可能性比较低
valid函数用于与空白格交换的格子的合法性
equal用于判断四个字符是否相等
check用于判断是否为最终局面
gethash用于计算局面的哈希值
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 |
#include<map> #include<set> #include<cmath> #include<stack> #include<queue> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define pi acos(-1) #define inf 1000000000 #define ll long long #define mod 9875321 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int head,tail=2,ans=-1; bool mp[10000005],last[1000005]; int xx[4]={0,0,1,-1},yy[4]={-1,1,0,0}; char a[5][5]; char q[1000005][5][5]; int step[1000005]; bool valid(int x,int y,int t) { if(x>4||y>4||x<1||y<1||a[x][y]=='O')return 0; if(a[x][y]=='B'&&t==0)return 0; if(a[x][y]=='W'&&t==1)return 0; return 1; } bool equal(char a,char b,char c,char d) { if(a!=b||b!=c||c!=d)return 0; return 1; } bool check(char a[5][5]) { for(int i=1;i<=4;i++) { if(equal(a[i][1],a[i][2],a[i][3],a[i][4]))return 1; if(equal(a[1][i],a[2][i],a[3][i],a[4][i]))return 1; } if(equal(a[1][1],a[2][2],a[3][3],a[4][4]))return 1; if(equal(a[1][4],a[2][3],a[3][2],a[4][1]))return 1; return 0; } int gethash(char a[5][5]) { int t=0,key=0; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) { if(a[i][j]=='O')t=0; if(a[i][j]=='W')t=1; if(a[i][j]=='B')t=2; key=(key*3+t)%mod; } return key; } void move(int x,int y) { for(int k=0;k<4;k++) { int tx=x+xx[k],ty=y+yy[k]; if(!valid(tx,ty,last[head]))continue; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) a[i][j]=q[head][i][j]; swap(a[x][y],a[tx][ty]); if(mp[gethash(a)])continue; mp[gethash(a)]=1; tail++; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) q[tail][i][j]=a[i][j]; step[tail]=step[head]+1; last[tail]=last[head]^1; if(check(a))ans=step[tail]; } } void bfs() { while(head!=tail) { for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) if(q[head][i][j]=='O') move(i,j); if(ans!=-1)return; head++; } } int main() { for(int i=1;i<=4;i++) scanf("%s",a[i]+1); for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) q[0][i][j]=q[1][i][j]=a[i][j]; last[0]=0;last[1]=1; bfs(); printf("%d",ans); return 0; } |
Subscribe
计数器 9854399
OI 课件=>
OI 课件=>