剑指offer-机器人的运动范围

剑指offer-机器人的运动范围

题目描述：

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

思路分析：

很正常的一道网格搜索题，用BFS或者DFS可以解决，在搜索的过程中，判断位置的和是不是满足题目要求即可，就当总结DFS和BFS的模板。

代码：

我自己的代码：

class Solution {
    int[] dx = new int[]{0,0,1,-1};
    int[] dy = new int[]{1,-1,0,0}; 
    int ans = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        bfs(m,n,0,0,k,visited);
        return ans;
    }
    private void dfs(int m, int n, int i, int j, int k, boolean[][] visited) {
        if(visited[i][j]) {
            return;
        }
        ans++;
        visited[i][j] = true;
        for(int kk = 0; kk < 4; kk ++) {
            int x = i + dx[kk], y = j + dy[kk];
            if(x < 0 || x >= m || y < 0 || y >= n || judge(x,y,k)) {
                continue;
            }
            dfs(m,n,x,y,k,visited);
        }
    }
    private void bfs(int m, int n, int i, int j, int k, boolean[][] visited) {
        Queue<postion> q = new LinkedList();
        q.offer(new postion(0,0));
        ans ++;
        visited[0][0] = true;
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-- > 0) {
                postion cur = q.poll();
                for(int kk = 0; kk < 4; kk++) {
                    int x = cur.x + dx[kk], y = cur.y + dy[kk];
                    if(x < 0 || x >=m || y < 0|| y >=n || judge(x,y,k) || visited[x][y]) {
                        continue;
                    }
                    visited[x][y] = true;
                    ans ++;
                    q.offer(new postion(x,y));
                }
            }
        }
    }
    private boolean judge(int x, int y,int k) {
        // 也不能进入行坐标和列坐标的数位之和大于k的格子
        int tmp = 0;
        while(x > 0) {
            tmp += x % 10;
            x /= 10;
        }
        while(y > 0) {
            tmp += y % 10;
            y /= 10;
        }
        return tmp > k;
    }
    class postion {
        int x;
        int y;
        public postion(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

网上别人的代码：

class Solution {
    int ans = 0;
    boolean[][] visited;
    int[] dx = new int[]{0,0,1,-1}, dy = new int[]{1,-1,0,0};
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        // dfs(0,0,m,n,k);
        bfs(m,n,k);
        return ans;
    }
    private void bfs(int m, int n, int k){
        Queue<pos> q = new LinkedList();
        q.offer(new pos(0,0));
        ans++;
        visited[0][0] = true;
        while(!q.isEmpty()){
            pos cur = q.poll();
            for(int i = 0;i < 4; i++){
                int x = cur.x + dx[i], y = cur.y + dy[i];
                if(x < 0 || x >= m || y < 0 || y >= n || visited[x][y]==true)
                    continue;
                visited[x][y] = true;
                if(!helper(x,y,k))
                    continue;
                ans ++;
                q.offer(new pos(x,y));
            }
        }
    }
    private void dfs(int i, int j, int m, int n, int k){
        if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j]==true)
            return;
        visited[i][j] = true;
        if(!helper(i,j,k)){
           return;
        }
        ans ++;
        dfs(i+0,j+1,m,n,k);

        dfs(i+0,j-1,m,n,k);

        dfs(i+1,j+0,m,n,k);

        dfs(i-1,j+0,m,n,k);

    }
    private boolean helper(int m, int n, int k){
        int sum = 0;
        while( m != 0 ){
            sum += m % 10;
            m = m / 10;
        }
        while( n != 0 ){
            sum += n % 10;
            n = n / 10;
        }
        return sum <= k;
    }

    class pos{
        int x;
        int y;
        public pos(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
}

AC记录：

赏

谢谢你请我吃糖果