您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【Lintcode】1367. Police Distance

题目地址:

https://www.lintcode.com/problem/1367/

给定一个 m × n m\times n m×n的矩阵,只含 1 , 0 , − 1 1,0,-1 1,0,1 1 1 1表示警察, 0 0 0表示空地, − 1 -1 1表示障碍物。求一个 m × n m\times n m×n的矩阵 A A A使得 A [ i ] [ j ] A[i][j] A[i][j]表示 ( i , j ) (i,j) (i,j)这个位置离其最近的警察与其的距离,距离取曼哈顿距离。障碍物的位置直接填 − 1 -1 1

从所有的警察开始做BFS即可。代码如下:

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    /**
     * @param matrix : the martix
     * @return: the distance of grid to the police
     */
    public int[][] policeDistance(int[][] matrix) {
        // Write your code here
        int m = matrix.length, n = matrix[0].length;
        int[][] res = new int[m][n];
        boolean[][] vis = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    vis[i][j] = true;
                } else if (matrix[i][j] == -1) {
                    res[i][j] = -1;
                }
            }
        }
        
        int dis = 0;
        int[] d = {1, 0, -1, 0, 1};
        while (!queue.isEmpty()) {
            dis++;
            for (int i = queue.size(); i > 0; i--) {
                int[] cur = queue.poll();
                int x = cur[0], y = cur[1];
                for (int j = 0; j < 4; j++) {
                    int nextX = x + d[j], nextY = y + d[j + 1];
                    if (0 <= nextX && nextX < m && 0 <= nextY && nextY < n && matrix[nextX][nextY] == 0 && !vis[nextX][nextY]) {
                        res[nextX][nextY] = dis;
                        vis[nextX][nextY] = true;
                        queue.offer(new int[]{nextX, nextY});
                    }
                }
            }
        }
        
        return res;
    }
}

时空复杂度 O ( m n ) O(mn) O(mn)


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进