March 31, 2015
Question is from careercup:
http://www.careercup.com/question?id=4716965625069568
Given a 2-D matrix represents the room, obstacle and guard like the following (0 is room, B->obstacle, G-> Guard): 0 0 0 B G G B 0 0 calculate the steps from a room to nearest Guard and set the matrix, like this 2 1 1 B G G B 1 1 Write the algorithm, with optimal solution.
题目：有一个二维矩阵表示的迷宫，其中G表示保安人员，B表示不可穿越的墙，其他位置均为空地。如果每次可以向东南西北四个方向移动一格，请计算出每个空格离最近的保安有多远。题目给出了一个示例。
解法：既然矩阵里可能有多个保安，我的思路是以各个保安为中心，进行广度优先搜索，搜索的过程中随时更新每个空格位置的最短距离，保证全部搜索完之后所有的结果都是最小的。单次BFS的时间代价是O(n^2)级别的。
Read the blog, and understand the solution; and then, implement it using C#
Try to implement the algorithm, so excited to practice a question used by Google interview. 体验Google面试题.
Share code written in C# language:
No comments:
Post a Comment