劍指Offer系列(java版,詳細解析)13.機器人的運動範圍

程序員社區 2022-01-08 04:27:57 阅读数:798

offer 系列 java 解析

題目描述

劍指 Offer 13. 機器人的運動範圍

難度中等232

地上有一個m行n列的方格,從坐標 [0,0] 到坐標 [m-1,n-1] 。一個機器人從坐標 [0, 0]的格子開始移動,它每次可以向左、右、上、下移動一格(不能移動到方格外),也不能進入行坐標和列坐標的數比特之和大於k的格子。例如,當k為18時,機器人能够進入方格 [35, 37] ,因為3+5+3+7=18。但它不能進入方格 [35, 38],因為3+5+3+8=19。請問該機器人能够到達多少個格子?

示例 1:

輸入:m = 2, n = 3, k = 1輸出:3

示例 2:

輸入:m = 3, n = 1, k = 0輸出:1

提示:

  • 1 <= n,m <= 100
  • 0 <= k <= 20

測試用例

  • 功能測試(方格為多行多列;k為正數)
  • 邊界值測試(方格只有一行或者只有一列;k等於0)
  • 特殊輸入測試(k為負數)

題目考點

  • 考察應聘者對回溯法的理解。通常物體或者人在二維方格運行這類問題都可以使用回溯法解决。
  • 考察應聘者對數組的編程能力。我們一般都把矩陣看成一個二維數組。只有對數組的特性充分了解,只有可能快速、正確得實現回溯法的代碼。

解題思路

和回溯法類似的遞歸,只是這裏不用回滾。

class Solution {
 int sums(int x ) {
 int s=0; while(x!=0){
 s+=x%10; x=x/10; } return s; } int k,m,n; 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]; return dfs(0,0); } private int dfs(int i, int j ){
 if(i>=m||j>=n|k<(sums(i)+sums(j))||visited[i][j]) return 0; visited[i][j]=true; return 1+dfs(i+1,j)+dfs(i,j+1); }}

廣度優先搜索方法

import java.util.LinkedList;/** * Author:Viper * Data:2021/3/11 * description: */public class problem13 {
 int sums(int x ) {
 int s=0; while(x!=0){
 s+=x%10; x=x/10; } return s; } public int movingCount(int m,int n,int k){
 boolean[][] visited=new boolean[m][n]; int res =0; LinkedList<int[]> queue = new LinkedList<>(); queue.add(new int[]{
0,0}); while(!queue.isEmpty()){
 int[] x = queue.poll(); int i=x[0],j=x[1]; if(i>=m||j>=n||k<(sums(i)+sums(j))||visited[i][j]) continue; visited[i][j]=true; res++; queue.add(new int[]{
i+1,j}); queue.add(new int[]{
i,j+1}); } return res; }}
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080427569579.html