本文共 2078 字,大约阅读时间需要 6 分钟。
题目描述
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格(35,37),因为3+5+3+7 = 18。但是,它不能进入方格(35,38),因为3+5+3+8 = 19。请问该机器人能够达到多少个格子?
分析
与前面的文章类似,用回溯法可以解决。
m行n列的方格可以看成是m*n的矩阵。同样在这个矩阵中,除了边界上的格子之外其他格子都有四个相邻的格子。
机器人从坐标(0,0)开始移动。但它准备进入坐标为(i,j)的个姿势,通过检查坐标的数位和来判断机器人是否能够进入(之前是判断字符是否相同)。如果能够进入(i,j),则判断它的四个相邻的格子。递归实现。
牛客AC:
public class Solution { public int movingCount(int threshold, int rows, int cols) { if(threshold <= 0 || rows <= 0 || cols <= 0) return 0; boolean[] visitFlags = new boolean[rows * cols]; // 元素是否访问过标识 return movingCountCore(threshold, rows, cols, 0, 0, visitFlags); } public int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visitFlags) { int count = 0; // 如果当前元素符合条件,则判断钙元素相邻的4个元素 if(check(threshold, rows, cols, row, col, visitFlags)) { int index = row * cols + col; visitFlags[index] = true; count = 1 + movingCountCore(threshold, rows, cols, row, col + 1, visitFlags) + movingCountCore(threshold, rows, cols, row, col - 1, visitFlags) + movingCountCore(threshold, rows, cols, row + 1, col, visitFlags) + movingCountCore(threshold, rows, cols, row - 1, col, visitFlags); } return count; } // 判断row,col的元素是否符合要求 public boolean check(int threshold, int rows, int cols, int row, int col, boolean[] visitFlags) { int index = row * cols + col; // 索引值在有效范围内、元素尚未访问、各位数和小于等于阈值 if(row >= 0 && row < rows && col >= 0 && col < cols && !visitFlags[index] && (getDigitsSum(row) + getDigitsSum(col)) <= threshold ) { return true; } return false; } // 计算num的各位数和 public int getDigitsSum(int num) { if(num <= 0) return 0; int sum = 0; while(num > 0) { sum += num % 10; num /= 10; } return sum; }}
参考
1. 何海涛,剑指offer名企面试官精讲典型编程题(纪念版),电子工业出版社转载地址:http://qkxgi.baihongyu.com/