首页 > 代码库 > codevs1004四子连棋[BFS 哈希]

codevs1004四子连棋[BFS 哈希]

2024-08-15 07:53:04   211人阅读

1004 四子连棋 

 时间限制: 1 s 
 空间限制: 128000 KB 
 题目等级 : 黄金 Gold
 
题目描述 Description

在一个4*4的棋盘上摆放了14颗棋子，其中有7颗白色棋子，7颗黑色棋子，有两个空白地带，任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格，这叫行棋一步，黑白双方交替走棋，任意一方可以先走，如果某个时刻使得任意一种颜色的棋子形成四个一线（包括斜线），这样的状态为目标棋局。

●○● 
○●○●
●○●○
○●○ 

 

输入描述 Input Description
从文件中读入一个4*4的初始棋局，黑棋子用B表示，白棋子用W表示，空格地带用O表示。
输出描述 Output Description

用最少的步数移动到目标棋局的步数。

样例输入 Sample Input

BWBO
WBWB
BWBW
WBWO

样例输出 Sample Output

5

 

很像八数码问题，状态空间搜索

保存State一个二维数组，本次选的颜色，步数,(封装一个结构体也可以)，BFS就行了，每次从空白走

hash表来判重

手写队列一个好处是可以直接用队列的编号

 

PS：1从hzwer那里学了些命名

　　　2据说迭代加深也可以，感觉并不好写

////  main.cpp//  codevs1004////  Created by Candy on 9/29/16.//  Copyright © 2016 Candy. All rights reserved.//#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N=5,MAXN=1e6,MOD=155333,hashsize=2e5;typedef int State[N][N];inline int read(){    char c=getchar();int x=0,f=1;    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}    return x;}int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0},ans=-1;char s[N];State q[MAXN];int head=1,tail=0,d[MAXN],col[MAXN];bool equ(char a,char b,char c,char d){    if(a!=b||b!=c||c!=d) return false;    return true;}bool check(State &a){    for(int i=1;i<=4;i++){        if(equ(a[i][1],a[i][2],a[i][3],a[i][4])) return 1;        if(equ(a[1][i],a[2][i],a[3][i],a[4][i])) return 1;    }    if(equ(a[1][1],a[2][2],a[3][3],a[4][4]))return 1;    if(equ(a[1][4],a[2][3],a[3][2],a[4][1]))return 1;    return 0;}bool valid(int x,int y,int num){    if(x<1||x>4||y<1||y>4) return 0;    if(q[num][x][y]!=col[num]) return 0;    return 1;}int h[hashsize],ne[hashsize];void init(){memset(h,0,sizeof(h));}int gethash(State &s){    int x=0;    for(int i=1;i<=4;i++){        for(int j=1;j<=4;j++) x=x*3+s[i][j];        x%=MOD;    }    return x;}bool tti(int num){    int x=gethash(q[num]);    for(int i=h[x];i;i=ne[i])        if(memcmp(q[i],q[num],sizeof(q[num]))==0) return 0;    ne[num]=h[x];    h[x]=num;    return 1;}void move(int x,int y){    State &s=q[head];    for(int i=0;i<4;i++){        int nx=x+dx[i],ny=y+dy[i];        if(!valid(nx,ny,head)) continue;        State &t=q[++tail];        memcpy(t,s,sizeof(s));        swap(t[nx][ny],t[x][y]);        if(tti(tail)){            d[tail]=d[head]+1;            col[tail]=col[head]==1?2:1;        }        else tail--;        if(check(t)) ans=d[tail];    }}void bfs(){    while(head<=tail){        State &now=q[head]; //printf("head %d\n",head);        for(int i=1;i<=4;i++)            for(int j=1;j<=4;j++)                if(now[i][j]==0) move(i,j);        if(ans!=-1) return;        head++;    }}int main(int argc, const char * argv[]) {    State &a=q[++tail],&b=q[++tail];    for(int i=1;i<=4;i++){        scanf("%s",s+1);        for(int j=1;j<=4;j++){            if(s[j]==‘B‘) a[i][j]=b[i][j]=1;            else if(s[j]==‘W‘) a[i][j]=b[i][j]=2;            else if(s[j]==‘O‘) a[i][j]=b[i][j]=0;        }    }    col[1]=1;col[2]=2;    bfs();    printf("%d",ans);    return 0;}

 

　　

codevs1004四子连棋[BFS 哈希]


联系
我们