為一個(gè)優(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 個(gè)起點(diǎn)'H'，若干個(gè)座位'S'，墻壁'#'和行人'P'。

　　其中墻壁'#'和行人'P'是不可通過的區(qū)域。

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

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

　　算法分析

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

　　讀取字符地圖，并找到起點(diǎn)的位置。

　　從起點(diǎn)開始，遍歷該地圖，記錄到達(dá)每一個(gè)'S'的距離。

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

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

　　首先是數(shù)據(jù)的讀入，由于輸入數(shù)據(jù)中已經(jīng)明確的告訴了我們地圖為 N 行 M 列，所以我們只需要一行一行讀入字符串，并使用char map[N][M]保存該地圖。

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

　　之后再對(duì)整個(gè)map[i][j]進(jìn)行一次 O(mn) 的遍歷，找出起點(diǎn)的位置，并記錄下來。

　　我們用startX, startY 來記錄起點(diǎn)的坐標(biāo)。

　　startX = startY = 0;

　　// 讀入地圖

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

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

　　// 查找起點(diǎn)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;

　　}

　　第二步，尋找從起點(diǎn)(startX, startY)分別到每個(gè)'S'的最短路徑。這一步我們直接使用BFS對(duì)整個(gè)圖進(jìn)行一次遍歷。

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

　　初始化為step[i][j] = INT_MAX，默認(rèn)為任何點(diǎn)都無法到達(dá)。

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

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

　　當(dāng)map[i][j] = '#'或map[i][j] = 'P'時(shí)，step[i][j]直接等于INT_MAX，并且不擴(kuò)展新的節(jié)點(diǎn)。

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

　　最后當(dāng)沒有新的節(jié)點(diǎn)可以到達(dá)時(shí)，退出BFS，得到整個(gè)地圖的step[N][M]。

　　bool inMap(int x, int y) {

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

　　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; // 用一個(gè)vector來存儲(chǔ)BFS的隊(duì)列

　　void BFS(int startX, int startY) {

　　// 將起點(diǎn)存入隊(duì)列

　　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) {

　　// 擴(kuò)展新的節(jié)點(diǎn)

　　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;

　　// 當(dāng)發(fā)現(xiàn)是座位時(shí)，不再進(jìn)行擴(kuò)展

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

　　}

　　}

　　++i;

　　}

　　return ;

　　}

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

　　此時(shí)我們?nèi)匀槐闅v整個(gè)地圖，因?yàn)橹皇菣z查是否有相鄰的'S'，不需要考慮順序，所以我們按照i = 1..n, j = 1..m的順序就可以。

　　當(dāng)我們掃描到一個(gè)'S'時(shí)，首先判定其周圍是否還有其他'S'。由于對(duì)稱性，我們只需要檢查兩個(gè)方向即可。

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

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

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

　　int ret = INT_MAX;

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

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

　　// 當(dāng)前位置為S，且可以到達(dá)

　　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ì)就是一個(gè)裸的寬度優(yōu)先搜索，唯一需要注意的只有當(dāng)搜索到'S'時(shí)，不擴(kuò)展新的節(jié)點(diǎn)。