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

思路

• dfs,递归解法和非递归,本文给出一种面向对象的非递归求解方法，代码更具易读性，可理解。
  定义Node对象，把走过的Node加入到stack中，并使用一个二维数组来标记走过的Node。
• bfs

代码

递归dfs

public class Solution {
    int[][] visited;
    int cnt=0;
    int h;
    int w;
    int th;
    int[] dir=new int[]{-1,0,1,0,-1};
    public int movingCount(int threshold, int rows, int cols)
    {   if(threshold<0){return 0;}
        visited=new int[rows][cols];
        h=rows;
        w=cols;
        th=threshold;
        dfs(0,0);
        return cnt;
    }
    public void dfs(int i,int j){
        //越界检查
        if(i<0||j<0||i>=h||j>=w){return;}
        //是否访问过检查
        if(visited[i][j]==1){return;}
        //是否满足条件检查
        if(cal(i)+cal(j)>th){return;}
        visited[i][j]=1;
        cnt++;
        for(int k=0;k<4;k++){
            dfs(i+dir[k],j+dir[k+1]);
        }
    }
    //计算数位总和
    public int cal(int in){
        int cnt=0;
        while(in>0){
            cnt+=in%10;
            in/=10;
        }
        return cnt;
    }
}

面向对象

import java.util.Stack;
class Node {
    int x;
    int y;

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

public class Solution {
    public int xySum(int x, int y){
        int sum = 0;
        while (x != 0) {
            sum += x % 10;
            x = x / 10;
        }
        while (y != 0) {
            sum += y % 10;
            y = y / 10;
        }
        return sum;
    }


    public int movingCount(int threshold, int rows, int cols){
        if(threshold < 0){
            return 0;
        }
        Stack<Node> stack = new Stack<>();
        boolean[][] visited = new boolean[rows][cols];
        Node node = new Node(0, 0);
        stack.add(node);
                visited[0][0]=true;
        int cnt = 1;
        while (!stack.empty()) {
            Node temp = stack.peek();
            if(temp.x + 1 < cols && (!visited[temp.y][temp.x + 1]) && xySum(temp.x + 1, temp.y) <= threshold){
                visited[temp.y][temp.x + 1] = true;
                stack.add(new Node(temp.x + 1, temp.y));
                cnt++;
            }else if(temp.y+1 < rows && (!visited[temp.y + 1][temp.x]) && xySum(temp.x, temp.y + 1) <= threshold){
                visited[temp.y + 1][temp.x] = true;
                stack.add(new Node(temp.x, temp.y + 1));
                cnt++;
            }else{
                stack.pop();
            }
        }
        return cnt;
    }
}