四子连珠

题目描述

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

○ ● ○ ●

● ○ ● ○

○ ● ○

输入格式

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

输出格式

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

输入输出样例

输入

BWBO
WBWB
BWBW
WBWO

输出

5

题目题解

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

//#define fre yes

#include <queue>
#include <cstdio>

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<Node> 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;
}

「爆搜」LuoGu P2346 四子连珠

原文：https://www.cnblogs.com/Nicoppa/p/11467047.html