CS-OA cs-vo Faang

IMC Trading CS OA 记录,help

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.

Leave a Reply

Your email address will not be published. Required fields are marked *