BFS算法实战:洛谷P2346棋盘游戏最短步数解法详解与C++实现

贾蔷
• 阅读 6

BFS算法实战:洛谷P2346棋盘游戏最短步数解法详解与C++实现

一、问题描述与解题思路

洛谷P2346题目要求我们计算在一个4x4的棋盘上,通过移动棋子使得四个相同颜色的棋子连成一条直线(横、竖或对角线)所需的最少步数。棋盘上有黑色(B)、白色(W)棋子和空格(O),每次只能将相邻的自己颜色的棋子移动到相邻的空格。

二、完整代码实现(带详细注释)

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespACe std;

// 定义棋盘状态结构体
struct State {
    string board;  // 棋盘状态字符串
    int steps;     // 到达该状态的步数
    bool isBlack;  // 当前该谁走棋
};

// 检查是否达到目标状态(四个一线)
bool isGoal(const string& board) {
    // 检查所有行
    for (int i = 0; i < 4; ++i) {
        if (board[i*4] != 'O' && board[i*4] == board[i*4+1] && 
            board[i*4] == board[i*4+2] && board[i*4] == board[i*4+3])
            return true;
    }

    // 检查所有列
    for (int i = 0; i < 4; ++i) {
        if (board[i] != 'O' && board[i] == board[i+4] && 
            board[i] == board[i+8] && board[i] == board[i+12])
            return true;
    }

    // 检查对角线
    if (board[0] != 'O' && board[0] == board[5] && 
        board[0] == board[10] && board[0] == board[15])
        return true;
    if (board[3] != 'O' && board[3] == board[6] && 
        board[3] == board[9] && board[3] == board[12])
        return true;

    return false;
}

// 获取所有可能的下一步状态
vector<State> getNextStates(const State& current) {
    vector<State> nextStates;
    const string& board = current.board;
    char currentPlayer = current.isBlack ? 'B' : 'W';

    // 找到所有空格位置
    vector<int> emptyPos;
    for (int i = 0; i < 16; ++i) {
        if (board[i] == 'O') emptyPos.push_back(i);
    }

    // 对于每个空格,检查四周可以移动过来的棋子
    for (int pos : emptyPos) {
        int row = pos / 4;
        int col = pos % 4;

        // 检查四个方向
        int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        for (auto& dir : dirs) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            if (newRow >= 0 && newRow < 4 && newCol >= 0 && newCol < 4) {
                int newPos = newRow * 4 + newCol;
                if (board[newPos] == currentPlayer) {
                    // 可以移动这个棋子到空格
                    string newBoard = board;
                    swap(newBoard[newPos], newBoard[pos]);
                    nextStates.push_back({newBoard, current.steps + 1, !current.isBlack});
                }
            }
        }
    }

    return nextStates;
}

int bfs(const string& initialBoard) {
    queue<State> q;
    unordered_map<string, bool> visited;

    // 初始状态,黑方先走
    q.push({initialBoard, 0, true});
    // 白方先走的初始状态
    q.push({initialBoard, 0, false});
    visited[initialBoard + "1"] = true;  // 黑方先走的标记
    visited[initialBoard + "0"] = true;  // 白方先走的标记

    while (!q.empty()) {
        State current = q.front();
        q.pop();

        if (isGoal(current.board)) {
            return current.steps;
        }

        vector<State> nextStates = getNextStates(current);
        for (const State& next : nextStates) {
            string key = next.board + (next.isBlack ? "1" : "0");
            if (!visited.count(key)) {
                visited[key] = true;
                q.push(next);
            }
        }
    }

    return -1;  // 无解情况
}

int main() {
    string board;
    string line;

    // 读取4x4棋盘
    for (int i = 0; i < 4; ++i) {
        cin >> line;
        board += line;
    }

    int result = bfs(board);
    cout << result << endl;

    return 0;
}

三、算法核心解析

  1. 状态表示
    • 使用字符串表示棋盘状态,便于存储和比较
    • State结构体记录当前棋盘、步数和轮到哪方走棋
  2. BFS搜索过程
    • 从初始状态开始广度优先搜索
    • 每次扩展当前状态的所有可能合法移动
    • 使用队列保证按步数顺序搜索
  3. 目标检测
    • 检查所有行、列和对角线是否有四个相同非空格棋子
    • 一旦发现目标状态立即返回当前步数
  4. 避免重复搜索
    • 使用哈希表记录已访问状态
    • 状态键包含棋盘和当前玩家信息

四、复杂度分析与优化建议

  1. 时间复杂度
    • 最坏情况下需要遍历所有可能状态
    • 实际运行时间取决于棋盘的初始布局
  2. 空间复杂度
    • 需要存储所有已访问状态
    • 对于4x4棋盘,状态空间在可控范围内
  3. 优化建议
    • 可以考虑双向BFS优化
    • 使用更高效的状态哈希方法
    • 对于特定模式可以提前终止搜索

来源:BFS算法实战:洛谷P2346棋盘游戏最短步数解法详解与C++实现

点赞
收藏
评论区
推荐文章
Wesley13 Wesley13
3年前
Codevs 1159最大全0子矩阵
题目描述Description在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多。输入描述InputDescription输入文件第一行为整数N,其中1<N<2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开。输出描述OutputDescription
Wesley13 Wesley13
3年前
@codeforces
\toc\@descriptiontranslation@给定一个n\n的棋盘,并划定一些不能放棋子的矩形区域。现在要在棋盘上放最多的车~~(读作ju)~~,使得这些车两两之间不会攻击。input:第一行整数n——棋盘边长(1<n<
Wesley13 Wesley13
3年前
C语言—————三子棋游戏
三子棋游戏问题描述:3\3的棋盘中,只要一条线上出现三个一样的棋子就获胜(玩家或电脑);如果棋盘已经放满还未出现三个棋子一条线则打成平手。具体细节:1.初始化棋盘(用空格初始化)//初始化棋盘voidinitChess(charchessboxROWCOL){
Wesley13 Wesley13
3年前
C语言实战项目—扫雷小程序
扫雷游戏是微软自带的一款小游戏。扫雷游戏的玩法是,以9\9棋盘为例,棋盘上随机分布着10个地雷,玩家在棋盘上进行点击,如果被点击的格子是地雷,则玩家被炸“死”,游戏结束;如果被点击的格子上没有地雷,与被点击的格子相邻的格子(被点击格子的上下左右还有斜向,共八个格子)有地雷,则在被点击的格子上显示这些地雷的总数,如果与被点击的格子相邻的八个格子都没有地雷,则
贾蔷 贾蔷
1星期前
2023年GESP六级题解:洛谷P10108闯关游戏动态规划解法详解
一、题目解读本文针对2023年GESP六级题目“闯关游戏”(洛谷P10108)进行详细解析。题目要求玩家通过不同关卡路径选择,计算从起点到终点的最大得分。关卡间存在跳跃规则,需结合动态规划思想设计高效算法,最终输出最优得分。二、解题思路采用动态规划(Dyn
贾蔷 贾蔷
1星期前
棋盘翻转大师:力扣LCP41题"翻转黑白棋"深度解析
截图未命名.jpg棋盘翻转大师:力扣LCP41题"翻转黑白棋"深度解析递归算法方向向量力扣LCP41C第1张一、问题理解题目要求在一个黑白棋棋盘上找出一个空位('.'表示),当放置一个黑棋('X')后,能够翻转最多数量的白棋('O')。翻转规则遵循标准
深度学习 深度学习
1星期前
2024年蓝桥杯国赛A组题 九宫格全解析:基于BFS算法的代码实现与优化
2024年蓝桥杯国赛A组题九宫格全解析:基于BFS算法的代码实现与优化蓝桥杯国赛九宫格问题BFS算法代码解析解题步骤第1张一、题目解读2024年蓝桥杯国A的九宫格题目(对应洛谷P10578)要求通过旋转九宫格中的2x2区域,实现从初始状态到目标状态的转换,
贾蔷 贾蔷
4星期前
洛谷P11228地图探险题解(CSP-J 2024真题)
一、题目重述给定n×m的二维矩阵表示探险地图,每个格子可能是:平地('.')障碍物('')起点('S')终点('E')求从起点到终点的最短路径步数,无法到达则输出1。二、核心算法:BFS广度优先搜索选择原因:BFS是解决无权图最短路径问题的最优方案,时间复
贾蔷 贾蔷
1星期前
2023年GESP六级小杨握手问题(洛谷B3874):Fenwick树求解逆序对的代码解析
一、题目解读“小杨的握手问题”源自2023年GESP六级考试(对应洛谷题目B3874)。题目描述为:给定一个长度为N的排列,每次将当前数与之前未访问过的数握手,求总共握手次数。本质上是求排列中逆序对的个数,即统计每个数右侧比它小的元素数量。需设计高效算法在
贾蔷 贾蔷
1星期前
力扣120题终极攻略:动态规划解三角形最小路径和(C++实现)
一、问题描述给定一个三角形triangle,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的节点上。二、​​C​​解决方案(带注释)CincludeincludeusingnamespACestd;classSolutionpublic:i