洛谷P2346-四子连棋-题解

四子连棋

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

BWBO
WBWB
BWBW
WBWO

样例输出 #1

5

P2346 四子连棋 - 洛谷

思路

这题看到图片就应该很容易想到使用搜索了，看到使用最少的步数，又能很自然的结合广搜的性质想到用广搜了。我们可以把地图当成搜索的步数存入进去，当有一部满足条件的时候，当前步数就是最短步数了。需要注意的是，我们需要黑白棋交替走，也就是说，黑白棋先手的顺序会影响最终的答案，所以我们应该对黑棋先手搜索结果和白棋先手的搜索结果取 $min$

为了方便，我们先定义以下缩写和方向

using matrix = vector<vector<char> >;
using pos = pair<int, int>;
using node = pair<char, int>;
pos dxy[]{{1,  0},
          {-1, 0},
          {0,  1},
          {0,  -1}};

以及避免操作系统不同导致的输入错误问题，写一个自己的getchar

char getch() {
    int c;
    for (c = getchar(); c != 'B' and c != 'W' and c != 'O'; c = getchar());
    return char(c);
}

用于判断搜索当前节点的地图是否满足条件

bool isFindAnswer(const matrix &now) {
    if ((now[0][0] == now[1][1] and now[0][0] == now[2][2] and now[0][0] == now[3][3])
        or (now[0][3] == now[1][2] and now[0][3] == now[2][1] and now[0][3] == now[3][0]))
        return true;
    for (int i = 0; i < 4; i++)
        if ((now[i][0] == now[i][1] and now[i][0] == now[i][2] and now[i][0] == now[i][3])
            or (now[0][i] == now[1][i] and now[0][i] == now[2][i] and now[0][i] == now[3][i]))
            return true;
    return false;
}

搜索的框架

int bfs(const char &firstStep) {
    set<matrix> st;
    queue<pair<matrix, node> > q;
    q.emplace(mat, node{firstStep, 0});
    st.emplace(mat);
    while (not q.empty()) {
        matrix now = q.front().first;
        node step = q.front().second;
        q.pop();
        if (isFindAnswer(now))
            return step.second;
        //这里其实就是
		//for (int i = 0; i < 4; ++i)
		//    for (int j = 0; j < 4; ++i)
		//但是为缩进不超过三次才有了这个写法
        for (int i = 0; i < 16; ++i)
            eachSearch(q, st, i / 4, i % 4, now, step);
    }
    return INT32_MAX;
}

搜索的核心

void eachSearch(queue<pair<matrix, node> > &q, set<matrix> &st,
                const int &i, const int &j, matrix &now, const node &step) {
    //如果开始点不是空点，那交换不了，直接不搜索
    if (now[i][j] != 'O')
        return;
    for (auto &xy: dxy) {
        int px = i + xy.first, py = j + xy.second;
        if (px < 0 or py < 0 or px >= 4 or py >= 4 or now[px][py] == step.first)
            continue;
        swap(now[px][py], now[i][j]);
        //如果还没生成过这个地图
        if (not st.count(now)) {
            st.emplace(now);
            q.emplace(now,node{step.first == 'B' ? 'W' : 'B', step.second + 1});
        }
        swap(now[px][py], now[i][j]);
    }
}

最后就是主函数

int main() {
    for (int i = 0; i < 4; ++i) {
        mat[i].resize(4);
        for (int j = 0; j < 4; ++j)
            mat[i][j] = getch();
    }
    printf("%d", min(bfs('W'), bfs('B')));
    return 0;
}

完整代码

#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;
using matrix = vector<vector<char> >;
using pos = pair<int, int>;
using node = pair<char, int>;
pos dxy[]{{1,  0},
          {-1, 0},
          {0,  1},
          {0,  -1}};
matrix mat(4);

char getch() {
    int c;
    for (c = getchar(); c != 'B' and c != 'W' and c != 'O'; c = getchar());
    return char(c);
}

bool isFindAnswer(const matrix &now) {
    if ((now[0][0] == now[1][1] and now[0][0] == now[2][2] and now[0][0] == now[3][3])
        or (now[0][3] == now[1][2] and now[0][3] == now[2][1] and now[0][3] == now[3][0]))
        return true;
    for (int i = 0; i < 4; i++)
        if ((now[i][0] == now[i][1] and now[i][0] == now[i][2] and now[i][0] == now[i][3])
            or (now[0][i] == now[1][i] and now[0][i] == now[2][i] and now[0][i] == now[3][i]))
            return true;
    return false;
}

void eachSearch(queue<pair<matrix, node> > &q, set<matrix> &st,
                const int &i, const int &j, matrix &now, const node &step) {
    if (now[i][j] != 'O')
        return;
    for (auto &xy: dxy) {
        int px = i + xy.first, py = j + xy.second;
        if (px < 0 or py < 0 or px >= 4 or py >= 4 or now[px][py] == step.first)
            continue;
        swap(now[px][py], now[i][j]);
        if (not st.count(now)) {
            st.emplace(now);
            q.emplace(now,node{step.first == 'B' ? 'W' : 'B', step.second + 1});
        }
        swap(now[px][py], now[i][j]);
    }
}

int bfs(const char &firstStep) {
    set<matrix> st;
    queue<pair<matrix, node> > q;
    q.emplace(mat, node{firstStep, 0});
    st.emplace(mat);
    while (not q.empty()) {
        matrix now = q.front().first;
        node step = q.front().second;
        q.pop();
        if (isFindAnswer(now))
            return step.second;
        for (int i = 0; i < 16; ++i)
            eachSearch(q, st, i / 4, i % 4, now, step);
    }
    return INT32_MAX;
}

int main() {
    for (int i = 0; i < 4; ++i) {
        mat[i].resize(4);
        for (int j = 0; j < 4; ++j)
            mat[i][j] = getch();
    }
    printf("%d", min(bfs('W'), bfs('B')));
    return 0;
}

AC截图