手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

【Lintcode】1911. As Far from Land as Possible

时间:2021/6/6 5:02:59|来源:|点击: 次

题目地址:

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

给定一个 m × n m\times n m×n 0 − 1 0-1 01矩阵,求一个位置的 0 0 0,使得其与与其距离最近的 1 1 1的距离最小。返回这个最小距离。距离采用曼哈顿距离。若不存在则返回 − 1 -1 1

可以从所有的 1 1 1开始做BFS,找到走到最后走到的 0 0 0的距离是多少即可。代码如下:

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

public class Solution {
    /**
     * @param grid: An array.
     * @return: An integer.
     */
    public int maxDistance(int[][] grid) {
        // Write your code here.
        int m = grid.length, n = grid[0].length;
        boolean[][] vis = new boolean[m][n];
        // 将所有的1入队
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.offer(new int[]{i, j});
                    vis[i][j] = true;
                }
            }
        }
        
        // 不存在0,返回-1
        if (queue.size() == m * n) {
            return -1;
        }
        
        int res = -1;
        int[] d = {1, 0, -1, 0, 1};
        while (!queue.isEmpty()) {
            res++;
            for (int i = queue.size() - 1; i >= 0; i--) {
                int[] cur = queue.poll();
                for (int j = 0; j < 4; j++) {
                    int x = cur[0] + d[j], y = cur[1] + d[j + 1];
                    if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 0 && !vis[x][y]) {
                        queue.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        
        return res;
    }
}

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

Copyright © 2002-2019 某某自媒体运营 版权所有