每天一道剑指offer-机器人的运动范围

乔戈里

发布于 2019-03-04 17:18:29

3270

发布于 2019-03-04 17:18:29

文章被收录于专栏：Java那些事

机器人的运动范围

题目描述

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

解析

定义一个黑盒 walk(intthreshold,introws,intcols,inti,intj,boolean[]visited)，它表示统计从 rows行 cols列的矩阵中的 (i,j)开始所能到达的格子并返回，对于当前位置 (i,j)有如下判断：

(i,j)是否越界矩阵了
(i,j)是否已被统计过了
(i,j)的行坐标和列坐标的数位之和是否大于 k

如果通过了上面三重检查，则认为 (i,j)是可以到达的（ res=1），并标记 (i,j)的 visited为 true表示已被统计过了，然后对 (i,j)的上下左右的格子调用黑盒进行统计。

这里要注意的是，与上一题不同， visited不会在递归计算完子状态后被重置回 false，因为每个格子只能被统计一次。 visited的含义不一样

public int movingCount(int threshold, int rows, int cols){    
  if(threshold < 0 || rows < 0 || cols < 0){        
    return 0;    
  }    
  boolean[] visited = new boolean[rows * cols];    
  return walk(threshold, rows, cols, 0, 0, visited);
}
private int walk(int threshold, int rows, int cols, int i, int j, boolean[] visited){    
  if(!isLegalPosition(rows, cols, i, j) || visited[i * cols + j] == true       || bitSum(i) + bitSum(j) > threshold){        
    return 0;    
  }    
  int res = 1;    
  visited[i * cols + j] = true;    
  res += walk(threshold, rows, cols, i + 1, j, visited) +        walk(threshold, rows, cols, i - 1, j, visited) +        walk(threshold, rows, cols, i, j + 1, visited) +        walk(threshold, rows, cols, i, j - 1, visited);    
  return res;
}
private boolean isLegalPosition(int rows, int cols, int i, int j){    
  if(i < 0 || j < 0 || i > rows - 1 || j > cols - 1){        
    return false;    
  }    
  return true;
}
public int bitSum(int num){    
  int res = num % 10;    
  while((num /= 10) != 0){        
    res += num % 10;    
  }    
  return res;
}

出自：http://www.zhenganwen.top

已获授权

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-02-16，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自程序员乔戈里微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度