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