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

　　Description

　　Everyday Littile Hi and Little Ho meet in the school cafeteria to have lunch together. Thecafeteria 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ū)域。

　　假設在地圖中，只能沿著上下左右移動，且每移動一個單元格為 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 ]設定為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) {

　　// 將起點存入隊列

　　step[ startX ][ startY ] = 0;

　　seq.push_back( make_pair(startX, startY) );

　　int i = 0;

　　while (i < (int) seq.size()) {

　　for (int dr = 0; dr < 4; ++dr) {

　　// 擴展新的節(jié)點

　　int tempX = seq[i].first + dir[dr][0];

　　int tempY = seq[i].second + dir[dr][1];

　　if (inMap(tempX, tempY) && step[tempX][tempY] == INT_MAX) {

　　step[tempX][tempY] = step[ seq[i].first ][ seq[i].second ] + 1;

　　// 當發(fā)現(xiàn)是座位時，不再進行擴展

　　if (map[tempX][tempY] != 'S') seq.push_back( make_pair(tempX, tempY) );

　　}

　　}

　　++i;

　　}

　　return ;

　　}

　　最后一步判斷是否有兩個連續(xù)的'S'都可達。

　　此時我們?nèi)匀槐闅v整個地圖，因為只是檢查是否有相鄰的'S'，不需要考慮順序，所以我們按照i = 1..n, j = 1..m的順序就可以。

　　當我們掃描到一個'S'時，首先判定其周圍是否還有其他'S'。由于對稱性，我們只需要檢查兩個方向即可。

　　若存在，則表示這兩個'S'相鄰，此時我們檢查這兩個位置的step值。

　　如果兩個位置的step值都不等于INT_MAX，則說明這兩個位置都是可以到達的。我們根據(jù)這兩個位置的step和更新最優(yōu)解。

　　當遍歷完整個地圖后，也就找到了我們所需要尋找的最優(yōu)值。

　　int ret = INT_MAX;

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

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

　　// 當前位置為S，且可以到達

　　if (map[i][j] == 'S' && step[i][j] != 0) {

　　// 檢查下邊是否有相鄰S

　　if (map[i - 1][j] == 'S' && step[i - 1][j] != 0 && ans > step[i][j] + step[i - 1][j])

　　ret = step[i][j] + step[i - 1][j];

　　// 檢查右邊是否有相鄰S

　　if (map[i][j - 1] == 'S' && step[i][j - 1] != 0 && ans > step[i][j] + step[i][j - 1])

　　ret = step[i][j] + step[i][j - 1];

　　}

　　結(jié)果分析

　　本題本質(zhì)就是一個裸的寬度優(yōu)先搜索，唯一需要注意的只有當搜索到'S'時，不擴展新的節(jié)點。