题面描述

部门组织了一场技术研讨会议。会议室有 n 排、m 列，共计 n × m 个座位，用字符 'O' 和 'H' 表示：

'O' 表示该座位是一个空座位。 'H' 表示座位上坐着一位同事。 坐在 r 排 c 列的小塔希望计算自己的活动范围。小塔给自己设定了以下移动限制：

最多 向左移动 L 步。 最多 向右移动 R 步。 向上和向下移动的步数不受限制。

请你帮小塔计算他能够到达的座位个数（包括他自己的座位）。

思路

为了高效地遍历所有可能的可达座位，我们可以使用广度优先搜索 (BFS)。在 BFS 的过程中，需要记录每个位置到达时已经使用的左移步数和右移步数，以确保不超过 L 和 R 的限制。

算法步骤

1.输入读取与预处理：

读取 n, m，表示网格的行数和列数。 读取 r, c，表示起始位置，将其转换为 0-based 索引。 读取 L, R，表示最多向左和向右移动的步数。 读取接下来的 n 行，构建座位网格 grid。

2.处理起始位置：

如果起始位置为 'H'，将其临时设置为 'O'，以允许小塔从该位置开始移动。

3.初始化 BFS 所需的数据结构：

创建两个二维数组 min_l 和 min_r，用于记录每个座位到达时已使用的最少左移步数和右移步数。初始化为无穷大 (INF)。 将起始位置的 min_l[r][c] 和 min_r[r][c] 设为 0。 初始化一个队列 q，将起始状态 (r, c, 0, 0) 加入队列。

4.执行 BFS 遍历：

从队列中取出当前状态 (x, y, l_steps, r_steps)。 遍历四个可能的移动方向：上、下、左、右。 向上或向下：不改变 l_steps 和 r_steps。 向左：l_steps 增加 1。 向右：r_steps 增加 1。 对于每一个可能的移动，执行以下步骤： 边界检查：确保新的位置在网格内。 障碍物检查：新的位置必须为 'O'。 步数限制检查：移动后的 l_steps 和 r_steps 不超过 L 和 R。 步数优化检查：如果通过当前路径到达该位置的 l_steps 或 r_steps 更少，则更新 min_l 和 min_r，并将新的状态加入队列。

5.统计可达座位数量：

遍历整个网格，统计所有满足 min_l[i][j] <= L 且 min_r[i][j] <= R 的座位数量。

6输出结果：

输出统计得到的可达座位数量。

代码如下

python

from collections import deque
import sys

def main():
    # 读取输入
    n, m = map(int, input().split())  # 会议室的行数n和列数m
    r, c = map(int, input().split())  # 小塔的起始位置r行c列（1-based）
    L, R = map(int, input().split())  # 小塔最多向左移动L步，向右移动R步

    # 转换为0-based索引
    r -= 1
    c -= 1

    # 读取座位布局，每行m个字符
    s = []
    for _ in range(n):
        row = sys.stdin.readline().strip()
        s.append(row)

    # 如果起始座位是 'H'，将其设置为 'O' 以允许移动
    if s[r][c] == 'H':
        # 将字符串转换为列表，修改后再转换回字符串
        row_list = list(s[r])
        row_list[c] = 'O'
        s[r] = ''.join(row_list)

    # 初始化两个二维数组，记录每个座位到达时的最少左移步数和最少右移步数
    min_l = [[float('inf')] * m for _ in range(n)]
    min_r = [[float('inf')] * m for _ in range(n)]

    # 设置起始位置的左移和右移步数为0
    min_l[r][c] = 0
    min_r[r][c] = 0

    # 定义四个移动方向：下、上、右、左
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]

    # 初始化队列，并加入起始状态
    q = deque()
    q.append((r, c, 0, 0))  # (x, y, l_steps, r_steps)

    while q:
        x, y, l_steps, r_steps = q.popleft()

        # 遍历四个方向
        for i in range(4):
            qx = x + dx[i]
            qy = y + dy[i]

            # 检查是否在边界内
            if not (0 <= qx < n and 0 <= qy < m):
                continue

            # 检查座位是否为 'H'
            if s[qx][qy] == 'H':
                continue

            # 根据移动方向更新左移和右移步数
            new_l = l_steps
            new_r = r_steps
            if dy[i] == -1:
                # 向左移动，消耗一个左移步数
                new_l += 1
            elif dy[i] == 1:
                # 向右移动，消耗一个右移步数
                new_r += 1

            # 检查是否超过步数限制
            if new_l > L or new_r > R:
                continue

            # 如果通过当前路径到达的左移或右移步数更少，则更新
            if new_l < min_l[qx][qy] or new_r < min_r[qx][qy]:
                # 更新最少步数
                min_l[qx][qy] = min(new_l, min_l[qx][qy])
                min_r[qx][qy] = min(new_r, min_r[qx][qy])
                # 将新的状态加入队列
                q.append((qx, qy, new_l, new_r))

    # 统计可达的座位个数（包括起始座位）
    ans = 0
    for i in range(n):
        for j in range(m):
            if s[i][j] == 'O' and min_l[i][j] <= L and min_r[i][j] <= R:
                ans +=1

    # 输出结果
    print(ans)

if __name__ == "__main__":
    main()

c++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 读取输入
    int n, m;
    cin >> n >> m;  // 会议室的行数n和列数m
    
    int r, c;
    cin >> r >> c;  // 小塔的起始位置r行c列（1-based）
    
    int L, R;
    cin >> L >> R;  // 小塔最多向左移动L步，向右移动R步
    
    // 转换为0-based索引
    r -= 1;
    c -= 1;
    
    // 读取座位布局，每行m个字符
    vector<string> s(n);
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    
    // 如果起始座位是 'H'，将其设置为 'O' 以允许移动
    if(s[r][c] == 'H'){
        s[r][c] = 'O';
    }
    
    // 初始化两个二维数组，记录每个座位到达时的最少左移步数和最少右移步数
    const int INF = 1e9;
    vector<vector<int>> min_l(n, vector<int>(m, INF));
    vector<vector<int>> min_r(n, vector<int>(m, INF));
    
    // 设置起始位置的左移和右移步数为0
    min_l[r][c] = 0;
    min_r[r][c] = 0;
    
    // 定义四个移动方向：下、上、右、左
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    
    // 初始化队列，并加入起始状态
    // 使用元组 (x, y, l_steps, r_steps)
    queue<tuple<int, int, int, int>> q;
    q.emplace(r, c, 0, 0);
    
    while(!q.empty()){
        auto [x, y, l_steps, r_steps] = q.front();
        q.pop();
        
        // 遍历四个方向
        for(int i = 0; i < 4; i++){
            int qx = x + dx[i];
            int qy = y + dy[i];
            
            // 检查是否在边界内
            if(qx < 0 || qx >= n || qy < 0 || qy >= m){
                continue;
            }
            
            // 检查座位是否为 'H'
            if(s[qx][qy] == 'H'){
                continue;
            }
            
            // 根据移动方向更新左移和右移步数
            int new_l = l_steps;
            int new_r = r_steps;
            if(dy[i] == -1){
                // 向左移动，消耗一个左移步数
                new_l += 1;
            }
            else if(dy[i] == 1){
                // 向右移动，消耗一个右移步数
                new_r += 1;
            }
            
            // 检查是否超过步数限制
            if(new_l > L || new_r > R){
                continue;
            }
            
            // 如果通过当前路径到达的左移或右移步数更少，则更新
            if(new_l < min_l[qx][qy] || new_r < min_r[qx][qy]){
                if(new_l < min_l[qx][qy]){
                    min_l[qx][qy] = new_l;
                }
                if(new_r < min_r[qx][qy]){
                    min_r[qx][qy] = new_r;
                }
                // 将新的状态加入队列
                q.emplace(qx, qy, new_l, new_r);
            }
        }
    }
    
    // 统计可达的座位个数（包括起始座位）
    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i][j] == 'O' && min_l[i][j] <= L && min_r[i][j] <= R){
                ans++;
            }
        }
    }
    
    // 输出结果
    cout << ans << "\n";
    
    return 0;
}

java

import java.util.*;
import java.io.*;

public class Main {
    // 定义一个类来表示BFS中的状态
    static class State {
        int x; // 行索引
        int y; // 列索引
        int l_steps; // 剩余左移步数
        int r_steps; // 剩余右移步数
        
        State(int x, int y, int l_steps, int r_steps){
            this.x = x;
            this.y = y;
            this.l_steps = l_steps;
            this.r_steps = r_steps;
        }
    }

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader提高输入效率
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] parts = br.readLine().split(" ");
        int n = Integer.parseInt(parts[0]); // 会议室的行数n
        int m = Integer.parseInt(parts[1]); // 会议室的列数m
        
        parts = br.readLine().split(" ");
        int r = Integer.parseInt(parts[0]) -1; // 小塔的起始行索引（0-based）
        int c = Integer.parseInt(parts[1]) -1; // 小塔的起始列索引（0-based）
        
        parts = br.readLine().split(" ");
        int L = Integer.parseInt(parts[0]); // 小塔最多向左移动L步
        int R = Integer.parseInt(parts[1]); // 小塔最多向右移动R步
        
        // 读取座位布局，每行m个字符
        String[] s = new String[n];
        for(int i =0; i<n; i++){
            s[i] = br.readLine().trim();
        }
        
        // 如果起始座位是 'H'，将其设置为 'O' 以允许移动
        if(s[r].charAt(c) == 'H'){
            StringBuilder sb = new StringBuilder(s[r]);
            sb.setCharAt(c, 'O');
            s[r] = sb.toString();
        }
        
        // 初始化两个二维数组，记录每个座位到达时的最少左移步数和最少右移步数
        int INF = Integer.MAX_VALUE;
        int[][] min_l = new int[n][m];
        int[][] min_r = new int[n][m];
        for(int i=0; i<n; i++){
            Arrays.fill(min_l[i], INF);
            Arrays.fill(min_r[i], INF);
        }
        
        // 设置起始位置的左移和右移步数为0
        min_l[r][c] = 0;
        min_r[r][c] = 0;
        
        // 定义四个移动方向：下、上、右、左
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};
        
        // 初始化队列，并加入起始状态
        Queue<State> q = new LinkedList<>();
        q.offer(new State(r, c, 0, 0));
        
        while(!q.isEmpty()){
            State current = q.poll();
            int x = current.x;
            int y = current.y;
            int l_steps = current.l_steps;
            int r_steps = current.r_steps;
            
            // 遍历四个方向
            for(int i=0; i<4; i++){
                int qx = x + dx[i];
                int qy = y + dy[i];
                
                // 检查是否在边界内
                if(qx <0 || qx >=n || qy <0 || qy >=m){
                    continue;
                }
                
                // 检查座位是否为 'H'
                if(s[qx].charAt(qy) == 'H'){
                    continue;
                }
                
                // 根据移动方向更新左移和右移步数
                int new_l = l_steps;
                int new_r = r_steps;
                if(dy[i] == -1){
                    // 向左移动，消耗一个左移步数
                    new_l +=1;
                }
                else if(dy[i] == 1){
                    // 向右移动，消耗一个右移步数
                    new_r +=1;
                }
                
                // 检查是否超过步数限制
                if(new_l > L || new_r > R){
                    continue;
                }
                
                // 如果通过当前路径到达的左移或右移步数更少，则更新
                if(new_l < min_l[qx][qy] || new_r < min_r[qx][qy]){
                    if(new_l < min_l[qx][qy]){
                        min_l[qx][qy] = new_l;
                    }
                    if(new_r < min_r[qx][qy]){
                        min_r[qx][qy] = new_r;
                    }
                    // 将新的状态加入队列
                    q.offer(new State(qx, qy, new_l, new_r));
                }
            }
        }
        
        // 统计可达的座位个数（包括起始座位）
        int ans =0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(s[i].charAt(j) == 'O' && min_l[i][j] <= L && min_r[i][j] <= R){
                    ans++;
                }
            }
        }
        
        // 输出结果
        System.out.println(ans);
    }
}

JavaScript

const readline = require('readline');

function main() {
    const rl = readline.createInterface({
        input: process.stdin,
        output: process.stdout
    });

    const input = [];
    rl.on('line', (line) => {
        input.push(line.trim());
    });

    rl.on('close', () => {
        let idx = 0;
        // 读取n和m
        let [n, m] = input[idx++].split(' ').map(Number);
        // 读取r和c，并转换为0-based索引
        let [r, c] = input[idx++].split(' ').map(Number);
        r -=1;
        c -=1;
        // 读取L和R
        let [L, R] = input[idx++].split(' ').map(Number);
        // 读取座位布局
        let s = [];
        for(let i=0; i<n; i++){
            s.push(input[idx++].replace(/0/g, 'O')); // 将 '0' 转换为 'O'
        }
        // 如果起始座位是 'H'，将其设置为 'O' 以允许移动
        if(s[r][c] === 'H'){
            let rowList = s[r].split('');
            rowList[c] = 'O';
            s[r] = rowList.join('');
        }
        // 初始化min_l和min_r数组
        const INF = Number.MAX_SAFE_INTEGER;
        // 使用一维数组来模拟二维数组，提高访问效率
        let min_l = new Array(n * m).fill(INF);
        let min_r = new Array(n * m).fill(INF);
        min_l[r * m + c] = 0;
        min_r[r * m + c] = 0;
        // 定义四个移动方向：下、上、右、左
        const dx = [1, -1, 0, 0];
        const dy = [0, 0, 1, -1];
        // 初始化队列，并加入起始状态
        let q = [];
        let ptr = 0;
        q.push({x: r, y: c, l_steps: 0, r_steps: 0});
        while(ptr < q.length){
            let current = q[ptr++];
            let x = current.x;
            let y = current.y;
            let l_steps = current.l_steps;
            let r_steps = current.r_steps;
            // 遍历四个方向
            for(let i=0; i<4; i++){
                let qx = x + dx[i];
                let qy = y + dy[i];
                // 检查是否在边界内
                if(qx <0 || qx >=n || qy <0 || qy >=m){
                    continue;
                }
                // 检查座位是否为 'H'
                if(s[qx][qy] === 'H'){
                    continue;
                }
                // 根据移动方向更新左移和右移步数
                let new_l = l_steps;
                let new_r = r_steps;
                if(dy[i] === -1){
                    // 向左移动，消耗一个左移步数
                    new_l +=1;
                }
                else if(dy[i] ===1){
                    // 向右移动，消耗一个右移步数
                    new_r +=1;
                }
                // 检查是否超过步数限制
                if(new_l > L || new_r > R){
                    continue;
                }
                // 计算目标位置的索引
                let targetIdx = qx * m + qy;
                // 如果通过当前路径到达的左移或右移步数更少，则更新
                if(new_l < min_l[targetIdx] || new_r < min_r[targetIdx]){
                    if(new_l < min_l[targetIdx]){
                        min_l[targetIdx] = new_l;
                    }
                    if(new_r < min_r[targetIdx]){
                        min_r[targetIdx] = new_r;
                    }
                    // 将新的状态加入队列
                    q.push({x: qx, y: qy, l_steps: new_l, r_steps: new_r});
                }
            }
        }
        // 统计可达的座位个数（包括起始座位）
        let ans =0;
        for(let i=0; i<n; i++){
            for(let j=0; j<m; j++){
                let idx1 = i * m + j;
                if(s[i][j] === 'O' && min_l[idx1] <= L && min_r[idx1] <= R){
                    ans++;
                }
            }
        }
        // 输出结果
        console.log(ans);
    });

}

main();

题目内容

部门组织了一场技术研讨会议。会议室有 $n$ 排、$m$ 列，共计 $n×m$ 个座位，用'$O$'和'$H$'表示，'$O$'表示该座位是一个空座位，'$H$"表示座位上坐着一位同事。坐在 $r$ 排 $c$ 列的小明想计算自己的活动范围，他给自己限定了只能最多向左移动 $L$ 步，向右移动 $R$ 步，但是前后移动的步数不做限制；并且有同事所在的座位(即'$H$'所在位置)小明不方便经过。只要自己能到达的座位，都算在他的活动范围内。请你帮小明求出他能够到达的座位个数(包括小明自己的座位)

说明:

1、向左向右可以连续移动，也可以不连续移动。例如向左移动 $2$ 步，有 $2$ 种可能：

1)左边有 $2$ 个连续空位，所以向左连续移动 $2$ 步

2)左边有 $2$ 个不连续空位，所以移动路径中包含向上或向下移动若干步和向左移动 $2$ 步

2、左移的步数与偏移量无关，例如左移一步之后上移一步再右移一步，再左移一步，此时向左偏移量为 $1$ ，但是向左移动了 $2$ 步。

3、排特指面朝纸面的左右方向，列特指面朝纸面的上下方向;

输入描述

输入共 $3+n$ 行

首行有 $2$ 个整数，以空格分隔，分别是 $n$ 和 $m$ (代表会议室有 $n$ 排 $m$ 列)

第 $2$ 行有 $2$ 个整数，以空格分隔，分别是 $r$ 和 $c$ (代表小明在 $r$ 排 $c$ 列)

第 $3$ 行有 $2$ 个整数，以空格分隔，分别是 $L$ 和 $R$ (代表小明最多向左走 $L$ 步，向右走 $R$ 步)

下面 $n$ 行，每行 $m$ 个字符(用'$O$'和'$H$'组成，'$O$'代表空座位，'$H$'代表座位上存在同事)

数据范围：$1<=n$，$m<=2000$；$1<=r<=n$；$1<=c<=m$；$0<=L$，$R<=10^9$

输出描述

一个整数 $Ans$ (表示小明能够到达的座位个数）

样例1

输入

4 5
3 2
1 2
OOOOO
OHHHO
OOOHH
HOOOO

输出

10

说明

用 $X$ 号表示小明的活动范围，如下图

XXXOO

XHHHO

XXXHH

HXXXO

答共计 $10$ 个空座位

样例2

输入

4 4
2 2 
0 1
OOOO
OOHO
OOOO
OOOO

输出

7

说明

用 $X$ 号表示小明的活动范围，如下图

OXXO

OXHO

OXXO

OXXO

答共计 $7$ 个空座位