[leetcode/lintcode 题解] 阿里算法面试真题:扫雷-阿里云开发者社区

开发者社区> 算法编程> 正文
登录阅读全文

[leetcode/lintcode 题解] 阿里算法面试真题:扫雷

简介: [leetcode/lintcode 题解] 阿里算法面试真题:扫雷

描述
现在有一个简易版的扫雷游戏。你将得到一个n*m大小的二维数组作为游戏地图。
每个位置上有一个值(0或1,1代表此处没有雷,0表示有雷)。
你将获得一个起点的位置坐标(x,y),x表示所在行数,y表示所在列数(x,y均从0开始计数)。
若当下位置上没有雷,则上下左右四个方向均可以到达,若当下位置有雷,则不能再往新的方向移动。
返回所有可以到达的坐标。
0<n,m<=200.
答案返回一个任意顺序的数组,数组包括所有可以到达的位置坐标。

在线评测地址:领扣题库官网

样例1
输入: 
[[1,0,0,0],[1,0,0,0],[0,1,1,1],[0,1,0,0]]
[0,1]
输出: 
[[0,1]]
解释:
[0,1]位置上是0,不能再往新的地方走,只能到达这一个位置
样例2
输入: 
[[1,0,0,0],[1,0,0,0],[0,1,1,1],[0,1,0,0]]
[1,0]
输出: 
[[0,0],[1,0],[1,1],[2,0],[0,1]]
解释:
[1,0]位置上是1,所以可以走到[[0,0],[1,1],[2,0]],其中只有[0,0]位置上是1可以继续走到[0,1],然后不能再走了。

解法:
BFS (宽度优先搜索)
算法 / 数据结构:BFS / 队列

解题思路
首先将起点压入队列中,不断获取队首元素并弹出队列,判断当前点上下边界是否越界、是否为地雷、是否到达过,然后将下一个可到达的点压入队列中,直到队列为空。

复杂度分析:
时间复杂度:O(n*m)
n为矩阵的行,m为矩阵的列,最坏的情况就是所有点都要遍历一次。
空间复杂度:O(n*m)
n为矩阵的行,m为矩阵的列,最坏的情况就是所有点都要遍历一次,并记录在visited中。

源代码

public class Solution {
    /**
     * @param Mine_map: an array represents the map.
     * @param Start: the start position.
     * @return: return an array including all reachable positions.
     */
    public List<List<Integer>> Mine_sweeping(int[][] Mine_map, int[] Start) {
        
        Queue<List<Integer>> queue = new LinkedList<>();
        List<List<Integer>> answer = new ArrayList<>();
        Map<List<Integer>, Boolean> visited = new HashMap<>();
        int row = Mine_map.length;
        int col = Mine_map[0].length;
        
        queue.offer(Arrays.asList(Start[0], Start[1]));
        
        while (!queue.isEmpty()) {
            List<Integer> current = queue.poll();
            int curX = current.get(0);
            int curY = current.get(1);
            answer.add(Arrays.asList(curX, curY));
            if (Mine_map[curX][curY] == 0) {
                continue;
            }
            visited.put(Arrays.asList(curX, curY), true);
            if (curX - 1 >= 0 && !visited.containsKey(Arrays.asList(curX - 1, curY))) {
                visited.put(Arrays.asList(curX - 1, curY), true);
                queue.offer(Arrays.asList(curX - 1, curY));
            }
            if (curX + 1 < row && !visited.containsKey(Arrays.asList(curX + 1, curY))) {
                visited.put(Arrays.asList(curX + 1, curY), true);
                queue.offer(Arrays.asList(curX + 1, curY));
            }
            if (curY - 1 >= 0 && !visited.containsKey(Arrays.asList(curX, curY - 1))) {
                visited.put(Arrays.asList(curX, curY - 1), true);
                queue.offer(Arrays.asList(curX, curY - 1));
            }
            if (curY + 1 <col && !visited.containsKey(Arrays.asList(curX, curY + 1))) {
                visited.put(Arrays.asList(curX, curY + 1), true);
                queue.offer(Arrays.asList(curX, curY + 1));
            }
        }
        
        return answer;
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: