机器人的运动范围

[toc]

思路一

使用广度优先搜索，从[0,0]开始，将其放入队列中，然后在队列不为空的情况下判断当前节点是否被访问过或者是否可达，若没被访问过且可达则结果加一，然后看这个节点的右边或者下面是否访问过，若未访问过则加入队列中。

import java.util.*;
public class Solution {
   public static int movingCount(int threshold, int rows, int cols)
    {
       if(rows > 0 && cols > 0 ) return move(threshold, rows, cols);
       return 0;
    }

    public static int move(int threshold, int rows, int cols){
        int result = 0;
        LinkedList<int[]> queue = new LinkedList<>();
        boolean[][] isVisited = new boolean[rows][cols];
        queue.add(new int[]{0,0});
        while(queue.size() > 0){
            int[] ij = queue.pop();
            int i = ij[0];
            int j = ij[1];
            if(isVisited[i][j] || !isA(threshold, i, j)) continue;
            else{
                result += 1;
                isVisited[i][j] = true;
            }
            if(i+1 < rows && j < cols){
                queue.add(new int[]{i+1,j});
            }
            if(i < rows && j+1 < cols){
                queue.add(new int[]{i,j+1});
            }
        }

        return result;
    }

    public static boolean isA(int threshold, int row, int col){
        int result = 0;
        while(row > 0){
            result += row % 10;
            row = row / 10;
        }
        while(col > 0){
            result += col % 10;
            col = col / 10;
        }
        return threshold >= result;
    }
}

思路二

DFS，递归实现

import java.util.*;
public class Solution {
   public static int movingCount(int threshold, int rows, int cols)
    {
        boolean[][] isVisited = new boolean[rows][cols];
        return move(threshold, rows, cols, 0, 0, isVisited);
    }

    public static int move(int threshold, int rows, int cols, int row, int col, boolean[][] isVisited){
        int result = 0;
        if(row >= rows || col >= cols) return 0;
        if(isVisited[row][col] || !isA(threshold, row, col)) return 0;
        result = 1 + move(threshold, rows, cols, row+1, col, isVisited)
                    + move(threshold, rows, cols, row, col+1, isVisited);
        isVisited[row][col] = true;
        return result;
    }

    public static boolean isA(int threshold, int row, int col){
        int result = 0;
        while(row > 0){
            result += row % 10;
            row = row / 10;
        }
        while(col > 0){
            result += col % 10;
            col = col / 10;
        }
        return threshold >= result;
    }
}