身為一個優(yōu)秀的程序猿，我們自然要懂一些叼叼的算法，今天給大家介紹的就是微軟的一道線上筆試題的解析。

　　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'是不可通過的區(qū)域。

　　假設(shè)在地圖中，只能沿著上下左右移動，且每移動一個單元格為 1 步。

　　詢問從'H'點出發(fā)，是否能夠到達兩個相鄰的'S'，且需要移動的步數(shù)最少是多少。

　　算法分析

　　從題目當中，我們就可以知道本題需要做什么：

　　讀取字符地圖，并找到起點的位置。

　　從起點開始，遍歷該地圖，記錄到達每一個'S'的距離。

　　判斷是否有兩個相鄰的'S'都可達，若存在多個解，則需要找到最小的值。

　　那么我們就按照這三個步驟來解決這道題目。

　　首先是數(shù)據(jù)的讀入，由于輸入數(shù)據(jù)中已經(jīng)明確的告訴了我們地圖為 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對整個圖進行一次遍歷。

　　首先建立數(shù)組int step[N][M]，step[i][j]表示從起點到(i,j)的最少步數(shù)。

　　初始化為step[i][j] = INT_MAX，默認為任何點都無法到達。

　　開始遍歷時，將step[ startX ][ startY ]設(shè)定為0，并以(startX, startY)開始BFS整個地圖。

　　在遍歷整個地圖的過程中我們需要注意：

　　當map[i][j] = '#'或map[i][j] = 'P'時，step[i][j]直接等于INT_MAX，并且不擴展新的節(jié)點。

　　當map[i][j] = 'S'時，我們需要更新當前節(jié)點的step[i][j]信息，但是由于當小Hi和小Ho走到位置后就不會再進行移動，所以也不擴展新的節(jié)點。

　　最后當沒有新的節(jié)點可以到達時，退出BFS，得到整個地圖的step[N][M]。

　　bool inMap(int x, int y) {

　　// 在地圖內(nèi) && 不為墻壁同時也不為行人

　　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} }; // 方向數(shù)組

　　vector< pair > seq; // 用一個vector來存儲BFS的隊列

　　void BFS(int startX, int startY) {

　　// 將起點存入隊列