资讯详情

为一个优秀的程序猿，我们自然要懂一些叼叼的算法，今天给大家介绍的就是微软的一道线上笔试题的解析。

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 个起点，若干个座位，墙壁和行人。

其中墙壁和行人是不可通过的区域。

假设在地图中，只能沿着上下左右移动，且每移动一个单元格为 1 步。

询问从点出发，是否能够到达两个相邻的，且需要移动的步数最少是多少。

算法分析

从题目当中，我们就可以知道本题需要做什么：

读取字符地图，并找到起点的位置。

从起点开始，遍历该地图，记录到达每一个的距离。

判断是否有两个相邻的都可达，若存在多个解，则需要找到最小的值。

那么我们就按照这三个步骤来解决这道题目。

首先是数据的读入，由于输入数据中已经明确的告诉了我们地图为 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 i++)

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

// 查找起点H

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

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

if (map[i][j] == ) {

startX = i, startY = j;

break;

}

第二步，寻找从起点(startX, startY)分别到每个的最短路径。这一步我们直接使用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] = 时，step[i][j]直接等于INT_MAX，并且不扩展新的节点。

当map[i][j] = 时，我们需要更新当前节点的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] == );

}

const int dir[4][2] = { {0, -1}, {1, 0}, {0, 1}, {-1, 0} }; // 方向数组

vector pair // 用一个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 ++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] != ) seq.push_back( make_pair(tempX, tempY) );

}

}

++i;

}

return ;

}

最后一步判断是否有两个连续的都可达。

此时我们仍然遍历整个地图，因为只是检查是否有相邻的，不需要考虑顺序，所以我们按照i = 1..n, j = 1..m的顺序就可以。

当我们扫描到一个时，首先判定其周围是否还有其他。由于对称性，我们只需要检查两个方向即可。

若存在，则表示这两个相邻，此时我们检查这两个位置的step值。

如果两个位置的step值都不等于INT_MAX，则说明这两个位置都是可以到达的。我们根据这两个位置的step和更新最优解。

当遍历完整个地图后，也就找到了我们所需要寻找的最优值。

int ret = INT_MAX;

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

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

// 当前位置为S，且可以到达

if (map[i][j] == step[i][j] != 0) {

// 检查下边是否有相邻S

if (map[i - 1][j] == 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] == step[i][j - 1] != 0 ans step[i][j] + step[i][j - 1])

ret = step[i][j] + step[i][j - 1];

}

结果分析

本题本质就是一个裸的宽度优先搜索，唯一需要注意的只有当搜索到时，不扩展新的节点。