算法题之机器人运动范围问题

算法题之机器人运动范围问题

问题描述

思路分析

思路1:使用递归回溯法进行求解

代码实现

int moveCount; public int movingCount(int m, int n, int k) { //构造m行n列的二维数组: int[][] board = new int[m][n]; findMovingPath(0,0,m,n,board,k); return moveCount; } private Boolean findMovingPath(int row, int col, int m, int n, int[][] board, int k) { if (row < 0 || row >= m || col < 0 || col >= n || getSum(row,col) > k || board[row][col] == 1) { return false; } //进行计数器加1 moveCount++; //进行递归探路 board[row][col] = 1;//1表示已经走过该路 boolean isVisited = findMovingPath(row,col - 1,m,n,board,k) || findMovingPath(row,col + 1,m,n,board,k) || findMovingPath(row - 1,col,m,n,board,k) || findMovingPath(row + 1,col,m,n,board,k); //board[row][col] = temp;//走过的路不能还原,不然计数器会重复计数 return isVisited; } private int getSum(int row, int col) { int sum = 0; sum = sum + row % 10 + (row / 10) % 10 + (row / 100) % 10 + col % 10 + (col / 10) % 10 + (col / 100) % 10; return sum; }

方法2:使用DFS深度优先搜索

代码实现

//定义m,n,k接收传入的参数 int m, n, k; //定义一个访问标记二维数组 boolean[][] visited; public int movingCount(int m, int n, int k) { this.m = m; this.n = n; this.k = k; this.visited = new boolean[m][n]; //进行dfs,返回值即为机器人到达的格子数 return dfs(0, 0, 0, 0); } public int dfs(int i, int j, int si, int sj) { //因为不存在向左或者向上遍历,则不会出现i < 0或者j < 0的情况 if(i >= m || j >= n || k < si + sj || visited[i][j]) { return 0; } //将当前位置标记为已访问 visited[i][j] = true; //因为从[0,0]开始,所以dfs只存在向下和向右 //进行dfs递归调用,并将的到达的格个数加1 //这里进行行和列所有位数相加一个很巧妙的方法: (i + 1) % 10 :判断其是否能整除10,如果可以,则将其减去8;如果不可以,则将其加上1 //例如:i = 9 ; 9 + 1 = 10 % 10 != 0,则将其减8得到1.而我们的10的十位加上个位的和正是1. return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8); }