vivo 2021校招笔试真题

1、游戏地图路径

【题目描述】

vivo游戏中心的运营小伙伴最近接到一款新游戏的上架申请，为了保障用户体验，运营同学将按运营流程和规范对其做出分析评估。经过初步了解后分析得知，该游戏的地图可以用一个大小为 n*n 的矩阵表示，每个元素可以视为一个格子，根据游戏剧情设定其中某些格子是不可达的(比如建筑、高山、河流或者其它障碍物等)，现在请你设计一种算法寻找从起点出发到达终点的最优抵达路径，以协助运营小伙伴评估该游戏的可玩性和上手难度。

输入描述：

第一行表示矩阵大小 n，5 <="" 10000<="" span="">

第二行表示起点和终点的坐标

第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其他字母、非0数字、以及符号+、-、* 等等均表示普通可达格子，共有 n 行 n 列

输出描述：

输出最优路径的长度；若无法到达，则输出-1

备注：

最优即最短，寻找最优路径时只能按上下左右四个方向前进。

输入样例：

15

0 7 7 7

*5#++B+B+++++$3

55#+++++++###$$

###$++++++#+*#+

++$@$+++$$$3+#+

+++$$+++$+4###+

A++++###$@+$++A

+++++#++$#$$+++

A++++#+5+#+++++

+++$$#$++#++++A

+++$+@$###+++++

+###4+$+++$$+++

+#+3$$$+++$##++

+#*+#++++++#$$+

$####+++++++$##

3$+++B++B++++#5

输出样例：

【解题思路】
迷宫问题，用BFS或者DFS均可。

【参考代码】
#include 
      
using namespace std;
using pii = pair
      
       ;
int main() {
    int n;
    cin >> n;
    pii s;
    pii e;
    cin >> s.second >> s.first >> e.second >> e.first;
    string tmp;
    getline(cin, tmp);
    vectorm;
    for (int i = 0; i != n; ++i) {
        getline(cin, tmp);
        m.emplace_back(move(tmp));
    }
    int step = 0;
    deque visited(n, deque(n, false));
    pii direct[4] = {{1, 0}, {-1, 0},