給定一幅字符表示的地圖，其中包含有 1 個(gè)起點(diǎn)'H'，若干個(gè)座位'S'，墻壁'#'和行人'P'。

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

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

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

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

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

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

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

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

首先是數(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)的位置，并記錄下來(lái)。

我們用startX, startY 來(lái)記錄起點(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)都無(wú)法到達(dá)。

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

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

當(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)沒(méi)有新的節(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來(lái)存儲(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，則說(shuō)明這兩個(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];
        }