机器人的运动范围（回溯法和广度优先搜索）

回溯法

机器人从(0,0)开始运动，进入坐标（i,j）时判断能否进入，如果能进入，再判断能否进入四个相邻的格子。

class Solution { public int movingCount(int m, int n, int k) { if(k < 0 || m <=0 || n <=0) return 0; boolean[][] visited = new boolean[m][n]; return movingCountCore(visited,m,n,0,0,k); } private int movingCountCore(boolean[][] visited, int rows, int cols, int row, int col,int k){ int count = 0; if(check(visited,rows, cols, row, col, k)){ visited[row][col] = true; //只需向下或向右移动 count = 1 + movingCountCore(visited, rows,cols,row + 1, col, k) //下 + movingCountCore(visited, rows,cols,row, col + 1, k);//右 } return count; } private boolean check(boolean[][] visited,int rows, int cols ,int row, int col, int k){ return row < rows && row >=0 && col < cols && col >= 0 && !visited[row][col] && digitSum(row) + digitSum(col) <= k; } private int digitSum(int number){ int sum = 0; while(number > 0){ sum+= number % 10; number /= 10; } return sum; } } 

广度优先搜索

class Solution { public int movingCount(int m, int n, int k) { if(k < 0 || m <=0 || n <=0) return 0; boolean[][] visited = new boolean[m][n]; Queue<Pair<Integer,Integer>> queue = new LinkedList<>(); queue.add(new Pair(0,0)); int ans = 1; //定义两个方向：向右和向下 int[] dx = {0,1}; int[] dy = {1,0}; while(!queue.isEmpty()){ Pair<Integer,Integer> xy = queue.poll(); int x = xy.getKey(); int y = xy.getValue(); for(int i = 0; i < 2; i++){//i = 0:向右；i=1：向下 int tx = dx[i] + x; int ty = dy[i] + y; if(!check(visited, m, n, tx, ty, k)) continue; queue.add(new Pair<Integer,Integer>(tx, ty)); visited[tx][ty] = true; ++ans; } } return ans; } private boolean check(boolean[][] visited,int rows, int cols ,int row, int col, int k){ return row < rows && row >=0 && col < cols && col >= 0 && !visited[row][col] && digitSum(row) + digitSum(col) <= k; } private int digitSum(int number){ int sum = 0; while(number > 0){ sum+= number % 10; number /= 10; } return sum; } } 

本文地址：https://blog.csdn.net/renweiyi1487/article/details/107874823