1367. Police Distance

Description

中文English

Given a matrix size of n x m, element 1 represents policeman, -1 represents wall and 0 represents empty.
Now please output a matrix size of n x m, output the minimum distance between each empty space and the nearest policeman

• Given a matrix size of n x m， n <= 200，m <= 200.
• We guarantee that each empty space can be reached by one policeman at least.

Have you met this question in a real interview?  

Example

Given mat =

[
    [0, -1, 0],
    [0, 1, 1],
    [0, 0, 0]
]

return [[2,-1,1],[1,0,0],[2,1,1]].

The distance between the policeman and himself is 0, the shortest distance between the two policemen to other empty space is as shown above

Given mat =

[
    [0, -1, -1],
    [0, -1, 1],
    [0, 0, 0]
]

return [[5,-1,-1],[4,-1,0],[3,2,1]]

和walls and gates一样，这样额外做一个状态matrix，把police点定义为0，空闲点定义为inf。
还是从所有target/destination点开始，不是从出发点开始。
这种题也可以从每个出发点一个个的找最近的police，但会出现重复搜索。
这里的方法其实是用单独一个状态matrix记忆搜索过的地方，避免重复搜索，用空间复杂度换时间复杂度。 class Solution { public: /** * @param matrix : the martix * @return: the distance of grid to the police */ //BFS的典型应用。把这个研究透。 //BFS vs DFS //DFS 剥洋葱，按住一个点，一直剥到里；然后回来从另一个点再剥到里 //BFS 一圈圈的剥，先剥掉整个一圈再剥下一圈。考虑一圈上有很多动手的点，把这些点放入queue里。先把最外层所有的点存入queue，每当剥点最外层的一点后，把次外层的该点存入queue。这样保证最完成的所有点剥完后，开始次外层的点开始剥。 // BFS 是按层的，找最短路径的一般用它。 // DFS 是recursion遍历所有可能的一般用它。 struct node { int x, y; node(int a, int b){ this->x = a; this->y = b; } }; vector<vector<int> > policeDistance(vector<vector<int>> &matrix ) { int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};//matrix找周围四个的典型方法，上下左右 int n = matrix.size(); int m = matrix[0].size(); int sx, sy, ex, ey; vector<vector<int> > ans = matrix; //先把开始着手的点放入queue queue<node>nodequeue; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 1) { nodequeue.push(node(i, j)); ans[i][j] = 0; } else { if(matrix[i][j] == 0) { ans[i][j] = INT_MAX; } else { ans[i][j] = -1; } } } } //开始一层层的执行 while(!nodequeue.empty()) { node head = nodequeue.front(); nodequeue.pop(); node New = head; for (int i = 0; i < 4; i++) { New.x = head.x + dx[i]; New.y = head.y + dy[i]; if(New.x < 0 || New.x >= n || New.y < 0 || New.y >= m || matrix[New.x][New.y] == -1 || ans[New.x][New.y] <= ans[head.x][head.y]) {//是否有效的判断条件 case By case，整体框架一样。 continue; } ans[New.x][New.y] = ans[head.x][head.y] + 1; nodequeue.push(New); } } return ans; } };