IMC作为量化交易公司，它的OA难度并没有互联网大厂的高。

据悉，本次OA只有2道题，其中第一题是固定的，而第二题是多选一。

固定的题目是：

**Avoiding the monsters**

in this game a player beins on a two-dimensional grid of size nxm.One el of the grid is marked as the end and the player wants to reach this cel in the grid by moving up,down, eft orrehtHowever, some cels are occupied by monsters.The goal ofthe player is to reach the end cel using a path that maximizes the minimum distance rom any monster along that path

The distance between any two points on the grid with coordinates (X1, y) and (X, 2) is calculated as x -X2 + y -2), where a is the absolute value of integer .

Notes:

1.One can visit a cell with a monster if necessary, i.e. no other path exists.

2.A cell can be visited only once on a given path.

**Example**

Consider the following grid of size 4x4 where empty cells are free, S' indicates the start, indicates the end and 'X' indicates a monster:

The optimal path is sthown in the 'Cell' colum. Note. the cel coordinates ar even ast, cd where ris the index of the row and cis the index of the rolumn.Thus the monstersin the abovexample are located at (0, 3) and (1,2). Coordinates of any of the nearest monster is in 'Monster..

Return 2, the closest distance to any monster along the path

**Function Description**

Complete the function findBestPath in the editor below.

findBestPath has the following parameters:

int n: the number of rows in the grid

int m: the number of columns in the grid

int startRow: the row index of the starting position

int startColumn: the column index of the starting position

int endRow: the row index of the ending position

int endColumn: the column index of the ending position

int monsterRowlil: the row index of the ith monster

int monsterColumnfil: the column index of the ith monster

**Returns**

int: the largest possible minimum distance from a monster in any path from the starting point to the ending point

**Constraints**

·2snms200

0sstartRow endRow <n

0<startColumn endColumn <m

number of monsters ≤n *m -2

0monsterRowlil<n

0s monsterColumnlil < m

There is exactly one start cel

There is exactly one end cell

There is at least one monster

Every cell is exactly one of the following: empty, start, end, or has a monster

这题的第一个想法是使用BFS做，大家觉得呢，如果需要辅导或者帮助的话，请加我的微信timedgqb.