题面简述

该题是一个典型的最短路径问题。我们给定了一个包含陷阱的网格地图，任务是从网格的左上角 (0, 0) 出发，找到一条路径到达右下角 (M-1, N-1)，要求在路径上经过陷阱时消耗体力。每次移动只能是上下左右四个方向，移动到有陷阱的格子消耗1个体力值，移动到没有陷阱的格子不消耗体力。目标是找到最少体力消耗的路径。

解题思路

这个问题可以通过 广度优先搜索（BFS） 来解决。我们使用 BFS 来进行层级遍历，从起点 (0, 0) 开始，逐步探索每个可到达的点，并更新从起点到每个点的最小体力消耗。

具体思路：

1. 网格表示：我们使用一个二维数组表示网格，每个格子可以是 'o' 表示无陷阱，或者 'u' 表示有陷阱。
2. BFS遍历：从起点 (0, 0) 开始，进行 BFS 遍历，队列中存储当前坐标和消耗的体力值。每次从队列中弹出当前坐标，探索其上下左右相邻的四个点。
3. 更新体力消耗：对于每个相邻点，如果当前位置是无陷阱，体力消耗不变；如果是陷阱，体力消耗增加1。
4. 最小体力：对于每个相邻点，只有当通过当前路径到达该点的体力消耗小于已知消耗时，才更新该点的体力消耗并将其加入队列。
5. 终止条件：当 BFS 完成，目标点 (M-1, N-1) 的体力消耗即为最少消耗体力值。

复杂度分析

• 时间复杂度：每个格子最多被访问一次，队列中的每个元素处理一次，因此时间复杂度为 O(M * N)，其中 M 和 N 是网格的行数和列数。
• 空间复杂度：需要一个二维数组 energy 来存储到每个点的最小体力消耗，空间复杂度为 O(M * N)。

代码实现

Python 代码

from collections import deque

def min_energy_to_reward(M, N, grid):
    # 定义四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # 初始化一个二维数组，记录到达每个位置的最小体力消耗
    energy = [[float('inf')] * N for _ in range(M)]
    
    # 队列，存储当前位置和当前消耗的体力
    queue = deque([(0, 0)])
    energy[0][0] = 1 if grid[0][0] == 'u' else 0
    
    while queue:
        x, y = queue.popleft()
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < M and 0 <= ny < N:
                # 如果当前位置有陷阱，消耗体力+1
                new_energy = energy[x][y] + (1 if grid[nx][ny] == 'u' else 0)
                if new_energy < energy[nx][ny]:
                    energy[nx][ny] = new_energy
                    queue.append((nx, ny))
    
    return energy[M-1][N-1]

# 输入处理
M, N = map(int, input().split())
grid = [input().strip() for _ in range(M)]

# 计算最小体力消耗
result = min_energy_to_reward(M, N, grid)
print(result)

Java 代码

import java.util.*;

public class Main {

    public static int minEnergyToReward(int M, int N, char[][] grid) {
        // 定义四个方向：上、下、左、右
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        // 初始化一个二维数组，记录到达每个位置的最小体力消耗
        int[][] energy = new int[M][N];
        for (int[] row : energy) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // 队列，存储当前位置
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0});
        energy[0][0] = (grid[0][0] == 'u')? 1 : 0;

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0], y = curr[1];

            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i], ny = y + dy[i];

                // 检查新的坐标是否在合法范围内
                if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
                    int newEnergy = energy[x][y] + (grid[nx][ny] == 'u' ? 1 : 0);
                    if (newEnergy < energy[nx][ny]) {
                        energy[nx][ny] = newEnergy;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }

        return energy[M-1][N-1];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        sc.nextLine();  // 消耗掉换行符

        char[][] grid = new char[M][N];
        for (int i = 0; i < M; i++) {
            grid[i] = sc.nextLine().toCharArray();
        }

        System.out.println(minEnergyToReward(M, N, grid));
    }
}

C++ 代码

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

int minEnergyToReward(int M, int N, vector<vector<char>>& grid) {
    // 定义四个方向：上、下、左、右
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    // 初始化一个二维数组，记录到达每个位置的最小体力消耗
    vector<vector<int>> energy(M, vector<int>(N, INT_MAX));

    // 队列，存储当前位置
    queue<pair<int, int>> q;
    q.push({0, 0});
    energy[0][0] = (grid[0][0] == 'u')? 1 : 0;

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        int x = curr.first, y = curr.second;

        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            // 检查新的坐标是否在合法范围内
            if (nx >= 0 && nx < M && ny >= 0 && ny < N) {
                int newEnergy = energy[x][y] + (grid[nx][ny] == 'u' ? 1 : 0);
                if (newEnergy < energy[nx][ny]) {
                    energy[nx][ny] = newEnergy;
                    q.push({nx, ny});
                }
            }
        }
    }

    return energy[M-1][N-1];
}

int main() {
    int M, N;
    cin >> M >> N;
    cin.ignore();  // 消耗掉换行符

    vector<vector<char>> grid(M, vector<char>(N));
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            cin >> grid[i][j];
        }
    }

    cout << minEnergyToReward(M, N, grid) << endl;

    return 0;
}

题目内容

部门年会组织了一个有奖活动:有一个包含陷阱的$M$行$N$列网格地图，需要从网格的左上角移动到右下角才算完成任务，可以领取奖励。活动规则为每次只能向上/向下/向左/向右移动一格。如果要移到无陷阱的位置，则体力无消耗;如果要移到有陷阱的位置，则需要消耗$1$个体力值。

问小明要领取奖励需要消耗的最少体力值。

输入描述

第一行输入$M$和$N(M≥1,N≥ 1,M +N≤20)$,使用空格分隔，表示网格有M行N列;

接下来输入一个$M$行$N$列的网格，网格中$u$表示该位置有陷阱，$o$表示无陷阱。

输出描述

领取奖励需要消耗的最少体力值

样例1

输入

3 5
ouuuu
uuuoo
oouuu

输出

4

说明

可以看出领取奖励消耗的最少体力路线有多条。例如第一条：$(0,0)-(1,0)-(2,0)-(2,1)-(2,2)-(2,3)-(2,4)$，只有$(1,0)、(2,2)、(2,3)、(2,4)$四个网格有陷阱;第二条：$(0,0)-(1,0)-(1,1)-(1,2)-(1,3)-(1,4)-(2,4)$，只有$(1,0)、(1,1)、(1,2)、(2,4)$四个网格有陷阱;因此小明领取奖励最少消耗$4$体力。

样例2

输入

4 4
oooo
uouu
uouo
uooo

输出

0