问题描述

题目要求在一个网格中找到一个最小分隔符，使得分隔符从网格的顶部开始，到底部结束，并且只能向下、向左或向右移动。分隔符将网格分为两个部分：左侧是集合 (W)，右侧是集合 (B)。我们需要通过调整分隔符中的节点，使得分隔符的节点数量最少，同时仍然保持分隔符的性质。

输入格式

• 第一行包含两个整数 (N) 和 (M)，表示网格的行数和列数。
• 接下来的 (N) 行，每行包含 (M) 个字符，字符可以是 'S'（分隔符）、'W'（左侧集合）或 'B'（右侧集合）。

输出格式

对于每个测试用例，输出一个整数，表示改进后分隔符中节点的最少数量。

解题思路

1. 预处理网格

   • 首先读取网格，并找到分隔符的起始位置。根据题目描述，分隔符从网格的顶行开始，且顶行中第一个 'S' 的位置即为起始位置。
   • 同时，将所有 'B' 转换为 'S'，如果它左边的节点是 'S'，这样可以简化后续的处理。

2. 广度优先搜索（BFS）

   • 使用 BFS 从分隔符的起始位置开始搜索。BFS 是一种适合解决最短路径问题的算法，这里用来找到从顶行到底行的最短路径。
   • 定义一个队列来存储当前节点及其步数。初始时，将起始位置加入队列。
   • 在 BFS 过程中，每次从队列中取出一个节点，检查其是否到达底行。如果到达底行，则更新答案。
   • 对于每个节点，尝试向下、向左和向右移动。如果移动后的节点是 'S' 且未被访问过，则将其加入队列。

3. 优化分隔符

   • 在 BFS 的过程中，我们实际上是在寻找从顶行到底行的最短路径。这个路径就是分隔符的最优路径。
   • BFS 的步数即为分隔符的长度。

代码分析

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>

using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大值，用于初始化答案

// 定义方向数组，表示可以向下、向左、向右移动
int dir[3][2] = {{1, 0}, {0, -1}, {0, 1}}; 

// 定义节点结构体，用于存储当前节点的坐标和步数
struct node
{
    int x, y, step;
};

// 广度优先搜索函数，用于找到从顶行到底行的最短路径
void bfs(int n, int m, char ch[205][205], int s, int &ans)
{
    queue<node> q; // 定义队列存储节点
    int visit[205][205] = {0}; // 初始化访问标记数组

    node pre, current; // 定义临时节点变量
    pre.x = 0; // 起始位置在顶行
    pre.y = s; // 起始列位置
    pre.step = 1; // 初始步数为1
    q.push(pre); // 将起始节点加入队列
    visit[0][s] = 1; // 标记起始位置已访问

    // 如果起始位置右边还有 'S'，也加入队列
    if (s + 1 < m - 1 && ch[0][s + 1] == 'S')
    {
        pre.x = 0;
        pre.y = s + 1;
        pre.step = 1;
        q.push(pre);
        visit[0][s + 1] = 1;
    }

    // 开始广度优先搜索
    while (!q.empty())
    {
        pre = q.front(); // 取出队列中的第一个节点
        q.pop();

        // 如果到达底行且不在角落，更新答案
        if (pre.x == n - 1 && pre.y > 0 && pre.y < m - 1)
        {
            ans = min(ans, pre.step); // 更新最短路径长度
            return;
        }

        // 遍历三个方向（下、左、右）
        for (int i = 0; i < 3; i++)
        {
            int xx = pre.x + dir[i][0], yy = pre.y + dir[i][1];
            // 如果已经访问过或超出边界，跳过
            if (visit[xx][yy] || xx < 0 || xx >= n || yy < 0 || yy >= m || ch[xx][yy] != 'S')
                continue;

            visit[xx][yy] = 1; // 标记当前节点已访问
            current.x = xx; // 更新当前节点坐标
            current.y = yy;
            current.step = pre.step + 1; // 步数加1
            q.push(current); // 将当前节点加入队列
        }
    }
}

int main()
{
    int n, m; // 网格的行数和列数
    char ch[205][205]; // 存储网格信息
    int s; // 分隔符的起始列位置

    // 多组输入
    while (~scanf("%d %d", &n, &m) && n && m)
    {
        // 读取网格信息
        for (int i = 0; i < n; i++)
        {
            scanf("%s", ch[i]);
            int flag = 0; // 标记是否已经处理过 'B' 转换为 'S'
            for (int j = 0; j < m; j++)
            {
                // 将符合条件的 'B' 转换为 'S'
                if (ch[i][j] == 'B' && ch[i][j - 1] == 'S' && !flag)
                {
                    ch[i][j] = 'S';
                    flag = 1;
                }
            }
        }

        // 找到分隔符的起始列位置
        for (int i = 0; i < m; i++)
        {
            if (ch[0][i] == 'S')
            {
                s = i;
                break;
            }
        }

        int ans = INF; // 初始化答案为无穷大
        bfs(n, m, ch, s, ans); // 调用 BFS 函数

        // 输出结果
        if (ans == INF)
        {
            printf("-1\n"); // 如果没有找到路径，输出 -1
        }
        else
        {
            printf("%d\n", ans); // 输出最短路径长度
        }
    }

    return 0;
}

代码说明

1. visit 数组：用于标记节点是否被访问过，避免重复访问。
2. dir 数组：定义了三个方向（下、左、右）。
3. bfs 函数：实现广度优先搜索，从起始位置开始，寻找最短路径。
4. main 函数：读取输入，预处理网格，调用 BFS 函数，并输出结果。

优化思路

• BFS 是解决最短路径问题的经典算法，时间复杂度为 (O(N \times M))，适合本题的规模。
• 预处理网格时，将符合条件的 'B' 转换为 'S'，可以简化分隔符的定义，避免额外的判断。

示例分析

以输入数据为例：

6 6  
WWSBBB  
WSSBBB  
WSBBBB  
WSBBBB  
WSSSBB  
WWWSBB  

• 预处理后，网格变为：

WWSBBB  
WSSBBB  
WSBBBB  
WSBBBB  
WSSSBB  
WWWSBB  

• BFS 的过程是从顶行的 'S' 开始，向下、左、右移动，找到最短路径。
• 最终答案为 7，表示改进后的分隔符中节点的最少数量。

总结

本题通过 BFS 算法解决了网格中的最短路径问题，结合预处理网格的技巧，可以高效地找到最小分隔符。