题目内容

小明在一个足球场上踢球。他需要绕过障碍物把球踢到门里。 足球场用大小为$M*M$的正方形网格表示，其中每个元素可以是空地、障碍物、球或者是球门:

• 小明用字母'$X$'表示，只要他在空地里面，就可以上下左右四个方向移动。

• 空地用字母'$0$'表示，在空地上可以自由行走。

• 障碍物用字母'$1$'表示，意味着不能通行，可能有多个障碍物。

题解

问题分析

在一个 m * m 的网格中，小明需要踢球，球经过障碍物和边界会停下。目标是计算小明将球踢入球门的最少踢球次数，若无法将球踢入球门则返回 -1。为了记录状态，我们需要四个变量来存储小明和球的位置。

解题思路:0-1 BFS

1. 多维度状态记录：
   • 使用 dist[x][y][fx][fy] 数组记录小明和球在不同位置的最小踢球次数。这里 x, y 表示小明的位置，fx, fy 表示球的位置。
   • 初始值 -1 表示该状态未被访问。