「爆搜」LuoGu P2346 四子连珠

四子连珠

题目描述

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

● ○ ●

○ ● ○ ●

● ○ ● ○

○ ● ○

输入格式

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

输出格式

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

输入输出样例

输入

BWBO
WBWB
BWBW
WBWO

输出

5

题目题解

很智障的爆搜题，不知道为什么是蓝题 我觉得黄题差不多了
但是！ 我也是个智障，我竟然忘了结构体可以单独分开来存QAQ 我还妄想用几个数组来维护整个棋盘 xxx
写了两个小时，还看了题解（quq我凉了

//#define fre yes#include 
#include const int N = 10;
char c[N][N];int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};struct Node {int t, last;int l[5], r[5];int a[N][N];bool check() {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 true;if (a[1][i] == a[2][i] && a[2][i] == a[3][i] && a[3][i] == a[4][i]) return true;}if (a[1][1] == a[2][2] && a[2][2] == a[3][3] && a[3][3] == a[4][4]) return true;if (a[4][1] == a[3][2] && a[3][2] == a[2][3] && a[2][3] == a[1][4]) return true;return false;}
} NEW;bool legal(Node k, int x, int y) {if(x >= 1 && y >= 1 && x <= 4 && y <= 4 && k.a[x][y] != 2) return true;return false;
}int bfs() {std::queue q;Node g1 = NEW; Node g2 = NEW;g1.last = 0; g2.last = 1;q.push(g1); q.push(g2);while(!q.empty()) {Node k = q.front();q.pop();for (int j = 1; j <= 2; j++) {int xx = k.l[j], yy = k.r[j];for (int i = 0; i < 4; i++) {int x = xx + dx[i];int y = yy + dy[i];if(legal(k, x, y) && k.a[x][y] != k.last) {Node w;w = k;std::swap(w.a[x][y], w.a[xx][yy]);w.l[j] = x; w.r[j] = y;w.last ^= 1;w.t += 1;if(w.check()) return w.t;q.push(w);}}}} return -1;
}int main() {for (int i = 1; i <= 4; i++) {scanf("%s", c[i] + 1);} for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if(c[i][j] == 'B') NEW.a[i][j] = 1;if(c[i][j] == 'W') NEW.a[i][j] = 0;if(c[i][j] == 'O') NEW.a[i][j] = 2; }}int xx = 0, yy = 0;for (int i = 1; i <= 4; i++) {for (int j = 1; j <= 4; j++) {if(NEW.a[i][j] == 2) {NEW.l[++xx] = i, NEW.r[++yy] = j;NEW.t = 0; NEW.last = 0;}}}printf("%d", bfs());return 0;
}

转载于:https://www.cnblogs.com/Nicoppa/p/11467047.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！