1004 四子连棋 (bfs)

叁歲伎倆 2022-06-16 12:51 144阅读 0赞

题目描述 Description

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

输入描述 Input Description

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

输出描述 Output Description

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

样例输入 Sample Input

BWBO  
WBWB  
BWBW  
WBWO

样例输出 Sample Output

数据范围及提示 Data Size & Hint

没有判重居然也过,等补充些哈希知识在补上判重部分

与八数码相似,但比八数码复杂一些

我写此题的思路流程

1->建立结构体，成员为该状态的地图map，步数step，分辨上次是哪个棋子落子的记号flag（flag为0时表示开场的第一次落子，为-1表示是前一次是黑子下的，为1表示

前一次是白子下的，因为要交替下棋，所以必须要设标记）

2->将棋盘转换成数值表示，1表示黑棋，2表示白棋， 0表示空格

3->进入bfs函数，用队列存储每种状态

4->具体的移动步骤：找出两个空格位置，空格位置找相应棋子进行移动，每次移动成功后判断是否连棋

代码：

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; struct node { int map[5][5]; //每种局面的地图 int flag; //-1是黑子下棋，1是白子下棋 int step; }s; int dir[4][2]={-1,0,0,1,1,0,0,-1},cst=0; queue<node> Q; /* 查看走每一步棋子的局面 void show(node temp) { int i,j; for (i=1; i<=4; i++) { for (j=1; j<=4; j++) { cout<<temp.map[i][j]; } cout<<endl; } cout<<temp.step<<endl; }*/ int check(node temp) { int i,j,k; for (i=1; i<=4 ;i++) { if (temp.map[i][1] == temp.map[i][2] && temp.map[i][2] == temp.map[i][3] &&temp.map[i][3] == temp.map[i][4]) { return 1; } if (temp.map[1][i] == temp.map[2][i] && temp.map[2][i] == temp.map[3][i] &&temp.map[3][i] == temp.map[4][i]) { return 1; } } if (temp.map[1][1] == temp.map[2][2] && temp.map[2][2] == temp.map[3][3] &&temp.map[3][3] == temp.map[4][4]) { return 1; } if (temp.map[1][4] == temp.map[2][3] && temp.map[2][3] == temp.map[3][2] &&temp.map[3][2] == temp.map[4][1]) { return 1; } return 0; } int bfs() { int i,j,k; int x1,y1,x2,y2;//两个空格的位置 int xx,yy; //新的方向 s.flag = 0; //先让flag为0，表示开始 黑白旗子 都可以走， //若flag为-1说明上次是黑棋走的，本次就应该让白棋走，不能让黑棋在走了 s.step = 0; Q.push(s); while(!Q.empty()) { node temp; temp = Q.front(); Q.pop(); if(check(temp)) //判断当前棋局 是否成立 { return temp.step; } //找出两个空格的位置 x1 = -1; for (i=1; i<=4; i++) { for (j=1; j<=4 ;j++) { if (temp.map[i][j]==0&&x1 == -1) { x1 = i; y1 = j; } else if (temp.map[i][j]==0) { x2 = i; y2 = j; break; } } } //进行移动 //黑子 在第一个空格位置上进行 移动 node t; for (j=0; j<4; j++) { if (temp.flag == -1) //因为黑白色要轮流走，上一次是黑色的，本次只能为白色 { break; } xx = dir[j][0]+x1; yy = dir[j][1]+y1; if (xx>=1 && xx<=4 && yy>=1&&yy<=4 && temp.map[xx][yy]==1) { t = temp; swap(t.map[xx][yy],t.map[x1][y1]); // 交换位置成为新状态的 t.flag=-1; t.step++; if (check(t)) { return t.step; } Q.push(t); } } //黑子在 第二个位置移动 for (j=0; j<4; j++) { if (temp.flag == -1) //因为黑白色要轮流走，上一次是黑色的，本次只能为白色 { break; } xx = dir[j][0]+x2; yy = dir[j][1]+y2; if (xx>=1 && xx<=4 && yy>=1&&yy<=4 && temp.map[xx][yy]==1) { t = temp; swap(t.map[xx][yy],t.map[x2][y2]); // 交换位置成为新状态的 t.step++; t.flag=-1; if (check(t)) { return t.step; } Q.push(t); } } //白子第一个空格位置移动 for (j=0; j<4; j++) { if (temp.flag == 1) //因为黑白色要轮流走，上一次是白色的，本次只能为黑色 { break; } xx = dir[j][0]+x1; yy = dir[j][1]+y1; if (xx>=1 && xx<=4 && yy>=1&&yy<=4 && temp.map[xx][yy]==2) { t = temp; swap(t.map[xx][yy],t.map[x1][y1]); // 交换位置成为新状态的 t.step++; t.flag=1; if (check(t)) { return t.step; } Q.push(t); } } //白子第2个空格位置移动 for (j=0; j<4; j++) { if (temp.flag == 1) //因为黑白色要轮流走，上一次是白色的，本次只能为黑色 { break; } xx = dir[j][0]+x2; yy = dir[j][1]+y2; if (xx>=1 && xx<=4 && yy>=1&&yy<=4 && temp.map[xx][yy]==2) { t = temp; swap(t.map[xx][yy],t.map[x2][y2]); // 交换位置成为新状态的 t.step++; t.flag=1; if (check(t)) { return t.step; } Q.push(t); } } } } int main() { char str[5]; for (int i=0; i<4; i++) { cin>>str; for (int j=0; j<4; j++) { if (str[j] == 'B') { s.map[i+1][j+1] = 1; } else if (str[j] == 'W') { s.map[i+1][j+1] = 2; } else { s.map[i+1][j+1] = 0; } } s.step = 0; } cout<<bfs()<<endl; return 0; }