题面简述

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

解题思路

这个问题可以通过 广度优先搜索（BFS） 来解决。我们使用 BFS 来进行层级遍历，从起点 (0, 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