- 相關(guān)推薦
微軟筆試題
為一個(gè)優(yōu)秀的程序猿，我們自然要懂一些叼叼的算法，今天給大家介紹的就是微軟的一道線(xiàn)上筆試題的解析。
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'是不可通過(guò)的區域。
假設在地圖中，只能沿著(zhù)上下左右移動(dòng)，且每移動(dòng)一個(gè)單元格為 1 步。
詢(xún)問(wèn)從'H'點(diǎn)出發(fā)，是否能夠到達兩個(gè)相鄰的'S'，且需要移動(dòng)的步數最少是多少。
算法分析
從題目當中，我們就可以知道本題需要做什么：
讀取字符地圖，并找到起點(diǎn)的位置。
從起點(diǎn)開(kāi)始，遍歷該地圖，記錄到達每一個(gè)'S'的距離。
判斷是否有兩個(gè)相鄰的'S'都可達，若存在多個(gè)解，則需要找到最小的值。
那么我們就按照這三個(gè)步驟來(lái)解決這道題目。
首先是數據的讀入，由于輸入數據中已經(jīng)明確的告訴了我們地圖為 N 行 M 列，所以我們只需要一行一行讀入字符串，并使用char map[N][M]保存該地圖。
map[i][j]表示原地圖的第i行第j列的信息。
之后再對整個(gè)map[i][j]進(jìn)行一次 O(mn) 的遍歷，找出起點(diǎn)的位置，并記錄下來(lái)。
我們用startX, startY 來(lái)記錄起點(diǎn)的坐標。
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對整個(gè)圖進(jìn)行一次遍歷。
首先建立數組int step[N][M]，step[i][j]表示從起點(diǎn)到(i,j)的最少步數。
初始化為step[i][j] = INT_MAX，默認為任何點(diǎn)都無(wú)法到達。
開(kāi)始遍歷時(shí)，將step[ startX ][ startY ]設定為0，并以(startX, startY)開(kāi)始BFS整個(gè)地圖。
在遍歷整個(gè)地圖的過(guò)程中我們需要注意：
當map[i][j] = '#'或map[i][j] = 'P'時(shí)，step[i][j]直接等于INT_MAX，并且不擴展新的節點(diǎn)。
當map[i][j] = 'S'時(shí)，我們需要更新當前節點(diǎn)的step[i][j]信息，但是由于當小Hi和小Ho走到位置后就不會(huì )再進(jìn)行移動(dòng)，所以也不擴展新的節點(diǎn)。
最后當沒(méi)有新的節點(diǎn)可以到達時(shí)，退出BFS，得到整個(gè)地圖的step[N][M]。
bool inMap(int x, int y) {
// 在地圖內 && 不為墻壁同時(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} }; // 方向數組
vector< pair
void BFS(int startX, int startY) {
// 將起點(diǎn)存入隊列
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) {
// 擴展新的節點(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;
// 當發(fā)現是座位時(shí)，不再進(jìn)行擴展
if (map[tempX][tempY] != 'S') seq.push_back( make_pair(tempX, tempY) );
}
}
++i;
}
return ;
}
最后一步判斷是否有兩個(gè)連續的'S'都可達。
此時(shí)我們仍然遍歷整個(gè)地圖，因為只是檢查是否有相鄰的'S'，不需要考慮順序，所以我們按照i = 1..n, j = 1..m的順序就可以。
當我們掃描到一個(gè)'S'時(shí)，首先判定其周?chē)欠襁�有其他'S'。由于對稱(chēng)性，我們只需要檢查兩個(gè)方向即可。
若存在，則表示這兩個(gè)'S'相鄰，此時(shí)我們檢查這兩個(gè)位置的step值。
如果兩個(gè)位置的step值都不等于INT_MAX，則說(shuō)明這兩個(gè)位置都是可以到達的。我們根據這兩個(gè)位置的step和更新最優(yōu)解。
當遍歷完整個(gè)地圖后，也就找到了我們所需要尋找的最優(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(chǎng)
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(chǎng)
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];
}
結果分析
本題本質(zhì)就是一個(gè)裸的寬度優(yōu)先搜索，唯一需要注意的只有當搜索到'S'時(shí)，不擴展新的節點(diǎn)。
【微軟筆試題】相關(guān)文章：
微軟招聘試題11-16
微軟的筆試試題02-18
用微軟試題膨脹你的思維11-11
微軟面試題（迷語(yǔ)篇)02-18
微軟招聘趣味邏輯測試題11-09
微軟公司秘密面試題！11-19
讓人頭疼的微軟面試題從哪里來(lái)02-24
微軟公司面試的智力測試題11-19