1.7 vivo求职攻略-理工科版本

1.7.1 校园招聘时间流程

1.7.2 薪资爆料

*数据来源 牛客用户，更多详细信息可到牛客查询

1.7.3 面试真题

1、游戏地图路径

【题目描述】

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

输入描述：

第一行表示矩阵大小 n，5 <n < 10000

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

第三行起是一个用矩阵表示的游戏地图，其中#或者@表示障碍物，其他字母、非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

输出样例：

13

【解题思路】

迷宫问题，用BFS或者DFS均可。

【参考代码】

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

int main() {

int n;

cin >> n;

pii s;

pii e;

cin >> s.second >> s.first >> e.second >> e.first;

string tmp;

getline(cin, tmp);

vector<string> m;

for (int i = 0; i != n; ++i) {

get