java calculates the range of motion of the robot

  • 2021-01-14 05:54:04
  • OfStack

The motion range of the robot java version is as follows

There is one m row and one n column square on the ground. A robot starts from the grid at coordinate 0,0, and can only move one grid in four directions each time, but it cannot enter a grid where the sum of row and column coordinates is greater than k. For example, when k is 18, the robot can enter the square (35,37) because 3+5+3+7 = 18. However, it cannot fit into the square (35,38), because 3+5+3+8 = 19. How many cells can the robot reach?

How to solve the problem:

1. First, judge whether the current position meets the entry conditions. If it meets the entry conditions, then continue to judge the four positions around it (except the boundary). If not, the current location is selected incorrectly.
2. On each attempt, declare an array of flags to record the locations that have been visited.
3. At present, there are three conditions for the attempt to continue: the position of the coordinate in the matrix is legal, the coordinate meets the entry condition, and the coordinate position has not been visited.


public class Solution {
 public int movingCount(int threshold, int rows, int cols)
 {
  if(threshold<0 || rows<=0 || cols<=0){
   return 0;
  }
  int count = 0;
  boolean[] flag = new boolean[rows*cols];
  for(int i=0; i<rows*cols; i++){
   flag[i] = true;
  }
  count = Moving(threshold, 0, 0, rows, cols, flag);
  return count;
 }

 public int Moving(int t, int row, int col, int rows, int cols, boolean[] flag){
  int count = 0;
  if(isAllow(t, row, col, rows, cols, flag)){
   flag[row*cols+col] = false;
   count = 1+Moving(t, row-1, col, rows, cols, flag)+Moving(t, row, col-1, rows, cols, flag)+Moving(t, row+1, col, rows, cols, flag)+Moving(t, row, col+1, rows, cols, flag);
  }
  return count;
 }

 // Computes the sum of the bits of the coordinate, and returns and threshold Comparison results of 
 public boolean isAllow(int t, int row, int col, int rows, int cols, boolean[] flag){
  if(row>rows ||row<0 || col>cols || col<0 || row*cols+col>rows*cols-1|| flag[row*cols+col]==false){
   return false;
  }
  int sum = 0;
  char[] chs = (row+"").toCharArray();
  char[] chs1= (col+"").toCharArray();
  for(char ch: chs){
   sum += Character.getNumericValue(ch);
  }
  for(char ch1: chs1){
   sum += Character.getNumericValue(ch1);
  }
  return sum<=t;
 }
}

Related articles: