机器人的运动范围

题目

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof

解法

解题思路：
本题与矩阵中的路径类似，是典型的矩阵搜索问题。此类问题通常可使用深度优先搜索（DFS）或广度优先搜索（BFS）解决。在介绍 DFS / BFS 算法之前，为提升计算效率，首先讲述两项前置工作：数位之和计算、搜索方向简化。

DFS

优化，机器人只能向下或者向右

class Solution {

    public int movingCount(int m, int n, int k) {
        // case 1
        int[][] map = new int[m][n];
        for(int i=0; i<m; i++){
            Arrays.fill(map[i], 1);
        }
        return dfs(map, k, 0, 0);
    }

    private int dfs(int[][] map, int k, int i, int j) {
        if (i<0 || i>=map.length || j<0 ||j>=map[0].length || sumPos(i, j) > k || map[i][j]!=1) {
            return 0;
        }
        int temp = map[i][j];
        map[i][j] = 0;
        return temp  + dfs(map, k, i+1, j) + dfs(map, k, i, j+1);
    }


    private int sumPos(int a, int b) {
        if(a < 0 || b < 0) return -1;
        int res=0;
        while(a != 0) {
            res += a %10;
            a /=10;
        }
        while(b != 0) {
            res += b%10;
            b /= 10;
        }
        return res;
    }
}

BFS

广度优先遍历 BFS
BFS/DFS ：两者目标都是遍历整个矩阵，不同点在于搜索顺序不同。DFS 是朝一个方向走到底，再回退，以此类推；BFS 则是按照“平推”的方式向前搜索。
BFS 实现：通常利用队列实现广度优先遍历。

public int movingCount2(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        int res = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{0,0});
        while (queue.size() > 0) {
            int[] x = queue.poll();
            int i = x[0], j = x[1];
            if (i>=m || j>= n || get(i, j)>k || visited[i][j] == true) {
                continue;
            }
            visited[i][j] = true;
            res++;
            queue.add(new int[]{i+1, j});
            queue.add(new int[]{i, j+1});
        }
        return res;
    }

2020-07-06

LC63_uniquePathsWithObstacles

机器人的运动范围

题目

解法

BFS

Links

Categorias

Nube de etiquetas

Recientes

Archivos

Etiquetas

Recientes

Archivos

Etiquetas

Your browser is out-of-date!