题目描述
地上有一个 m 行和 n 列的方格，横纵坐标范围分别是 0～m?1 和 0～n?1。
一个机器人从坐标 (0,0)的格子开始移动，每一次只能向左，右，上，下四个方向移动一格。
但是不能进入行坐标和列坐标的数位之和大于 k的格子。
请问该机器人能够达到多少个格子？
样例1
输入：k=7, m=4, n=5
输出：20
样例2
输入：k=18, m=40, n=40
输出：1484
解释：当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。
但是，它不能进入方格（35,38），因为3+5+3+8 = 19。
注意:
0<=m<=500<=n<=500<=k<=100
分析
典型的宽度优先搜索
闫式分析：
AC代码
1 import java.util.Queue; 2 import java.util.concurrent.LinkedBlockingQueue; 3 4 public class Main { 5 public static void main(String[] args) { 6 int movingCount = movingCount(7, 4, 5); 7 // int movingCount = t.movingCount(18, 40, 40); 8 System.out.println(movingCount); 9 } 10 11 public static int movingCount(int threshold, int rows, int cols) 12 { 13 if (rows == 0 || cols == 0) { 14 return 0; 15 } 16 if (threshold == 0) { 17 return 1; 18 } 19 boolean[][] visit = new boolean[rows][cols]; 20 return bfs(0, 0, threshold, rows, cols, visit); 21 } 22 23 /** 24 * 宽度优先搜索 25 * 定义方向：右、下、左、上 26 */ 27 public static int bfs(int start, int end, int threshold, int rows, int cols, boolean[][] visit) { 28 Queue<Point> queue = new LinkedBlockingQueue<>(); 29 // 将起点加入队列中 30 queue.add(new Point(start, end)); 31 // 统计走的格子数 32 int count = 0; 33 int[] x = {0, 1, 0, -1}; 34 int[] y = {1, 0, -1, 0}; 35 while (queue.size() > 0) { 36 // 出队列 37 Point cur = queue.poll(); 38 for (int k = 0; k < 4; k++) { 39 int nextX = cur.x + x[k]; 40 int nextY = cur.y + y[k]; 41 if (nextX >= 0 && nextX < rows && nextY >= 0 && nextY < cols && !visit[nextX][nextY]) { 42 int total = getPeriodNum(nextX, nextY); 43 if (total <= threshold) { 44 count++; 45 visit[nextX][nextY] = true; 46 // 入队列 47 queue.add(new Point(nextX, nextY)); 48 } 49 } 50 } 51 } 52 53 return count; 54 } 55 56 public static int getPeriodNum(int a, int b) { 57 int total = 0; 58 while (a != 0) { 59 total += a % 10; 60 a /= 10; 61 } 62 while (b != 0) { 63 total += b % 10; 64 b /= 10; 65 } 66 67 return total; 68 } 69 } 70 71 class Point { 72 int x; 73 int y; 74 public Point(int x, int y) { 75 this.x = x; 76 this.y = y; 77 } 78 }