微软笔试题分析

　　身为一个优秀的程序猿，我们自然要懂一些叼叼的算法，今天给大家介绍的就是微软的一道线上笔试题的解析。

　　Description

　　Everyday Littile Hi and Little Ho meet in the school cafeteria to have lunch together. The cafeteria is often so crowded that two adjacent seats are hard to find.

　　School cafeteria can be considered as a matrix of N*M blocks. Each block can be empty or occupied by people, obstructions and seats. Little Hi and Little Ho starts from the same block. They need to find two adjacent seats(two seats are adjacent if and only if their blocks share a common edge) without passing through occupied blocks. Further more, they want the total distance to the seats is minimal.

　　Little Hi and Little Ho can move in 4 directions (up, down, left, right) and they can not move outside the matrix.

　　题意分析

　　给定一幅字符表示的地图，其中包含有 1 个起点'H'，若干个座位'S'，墙壁'#'和行人'P'。

　　其中墙壁'#'和行人'P'是不可通过的区域。

　　假设在地图中，只能沿着上下左右移动，且每移动一个单元格为 1 步。

　　询问从'H'点出发，是否能够到达两个相邻的'S'，且需要移动的步数最少是多少。

　　算法分析

　　从题目当中，我们就可以知道本题需要做什么：

　　读取字符地图，并找到起点的位置。

　　从起点开始，遍历该地图，记录到达每一个'S'的距离。

　　判断是否有两个相邻的'S'都可达，若存在多个解，则需要找到最小的值。

　　那么我们就按照这三个步骤来解决这道题目。

　　首先是数据的读入，由于输入数据中已经明确的告诉了我们地图为 N 行 M 列，所以我们只需要一行一行读入字符串，并使用char map[N][M]保存该地图。

　　map[i][j]表示原地图的第i行第j列的信息。

　　之后再对整个map[i][j]进行一次 O(mn) 的遍历，找出起点的位置，并记录下来。

　　我们用startX, startY 来记录起点的坐标。

　　startX = startY = 0;

　　// 读入地图

　　for (int i = 1; i <= N; i++)

　　scanf("%s", map[i] + 1);

　　// 查找起点H

　　for (int i = 1; i <= N; i++)

　　for (int j = 1; j <= M; ++j)

　　if (map[i][j] == 'H') {

　　startX = i, startY = j;

　　break;

　　}

　　第二步，寻找从起点(startX, startY)分别到每个'S'的最短路径。这一步我们直接使用BFS对整个图进行一次遍历。

　　首先建立数组int step[N][M]，step[i][j]表示从起点到(i,j)的最少步数。

　　初始化为step[i][j] = INT_MAX，默认为任何点都无法到达。

　　开始遍历时，将step[ startX ][ startY ]设定为0，并以(startX, startY)开始BFS整个地图。

　　在遍历整个地图的过程中我们需要注意：

　　当map[i][j] = '#'或map[i][j] = 'P'时，step[i][j]直接等于INT_MAX，并且不扩展新的节点。

　　当map[i][j] = 'S'时，我们需要更新当前节点的step[i][j]信息，但是由于当小Hi和小Ho走到位置后就不会再进行移动，所以也不扩展新的节点。

　　最后当没有新的节点可以到达时，退出BFS，得到整个地图的step[N][M]。

　　bool inMap(int x, int y) {

　　// 在地图内 && 不为墙壁同时也不为行人

　　return (1 <= x && x <= N && 1 <= y && y <= M) && (map[x][y] == '.' || map[x][y] == 'S');

　　}

　　const int dir[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} }; // 方向数组

　　vector< pair > seq; // 用一个vector来存储BFS的队列

　　void BFS(int startX, int startY) {

　　// 将起点存入队列