給定一幅字符表示的地圖，其中包含有 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) {
    // 將起點存入隊列
    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];
        }