[[415476]]

本文轉(zhuǎn)載自微信公眾號「神奇的程序員K」，作者神奇的程序員K。轉(zhuǎn)載本文請聯(lián)系神奇的程序員K公眾號。

前言

有一個矩陣，機器人可以從坐標(0,0)的格子開始移動，它每次可以向左、右、上、下移動一格，但是不能進入行坐標和列坐標的數(shù)位之和大于K的格子，求這個機器人總共能走多少個格子以及它的行動軌跡。

本文就跟大家分享下這個問題的解決方案 ，歡迎各位感興趣的開發(fā)者閱讀本文。

實現(xiàn)思路

在上一篇講解尋找矩陣中的路徑文章中，我們學會了使用回溯算法來訪問矩陣中的格子，本文要討論的這個問題在訪問格子之前做了一層判斷，如果滿足條件就能進入，不滿足就無法進入。

我們要做的這層判斷為：計算出待訪問格子的坐標的數(shù)位之和，如果其大于K(最大活動范圍)則不能訪問。

數(shù)位之和：即取出數(shù)字中每個位置的值，將其相加得出的結果。例如：19的數(shù)位之和就是1 + 9 = 10。

判斷當前格子是否已訪問

首先，我們需要創(chuàng)建一個與原矩陣大小相同的矩陣，用于標識機器人是否已走這個格子。

在js中無法直接創(chuàng)建指定大小的二維數(shù)組，創(chuàng)建思路如下：

• 以矩陣的長度為大小創(chuàng)建一個數(shù)組
• 遍歷創(chuàng)建好的數(shù)組，再以矩陣的第0號數(shù)組的長度為大小創(chuàng)建數(shù)組，賦值給遍歷到的每一項。

判斷格子是否可進入

在訪問格子時，我們需要判斷下要訪問的格子是否能進入，我們需要計算出行坐標與列坐標的數(shù)位之和，然后將其相加，判斷相加后的結果是否大于機器人的最大活動范圍(K)。

計算數(shù)位之和有兩種做法：

• 將數(shù)字轉(zhuǎn)為字符串，遍歷取出每個字符將其轉(zhuǎn)為數(shù)字后再相加
• 對數(shù)字進行模運算，將其結果相加，再對數(shù)字本身進行/10操作，直至數(shù)字小于等于0

開始移動機器人

移動機器人時，我們需要7個參數(shù)：

• 矩陣的總行數(shù)
• 矩陣的總列數(shù)
• 即將進入格子的行坐標
• 即將進入格子的列坐標
• 最大活動范圍
• 訪問標識矩陣
• 路徑矩陣

首先，我們需要進行邊界條件判斷(遞歸的終止條件)，條件滿足代表該格子無法訪問，可行走格子為0(直接返回0)：

• 待訪問格子的行坐標大于矩陣的總行數(shù)
• 待訪問格子的行坐標小于0
• 待訪問格子的列坐標大于矩陣的總列數(shù)
• 待訪問格子的列坐標小于0
• 當前格子已經(jīng)被訪問
• 當前格子不能進入

如果上述條件都滿足則表示當前格子可以訪問，保存當前格子中的值到行動軌跡中，標識當前格子為已訪問狀態(tài)，已行走格子數(shù)+1，并遞歸嘗試當前格子的其它四個方向的格子能否進入。

當遞歸棧清空后，我們也就得到了機器人總共可以進入的格子總數(shù)以及它的行動軌跡。

實現(xiàn)代碼

接下來，我們將上述思路轉(zhuǎn)換為TypeScript代碼。

格子能否進入函數(shù)

我們先來看下判斷當前格子能否進入的函數(shù)實現(xiàn)，如下所示：

  /** 
   * 判斷機器人能否進入目標格子 
   * @param row 行坐標 
   * @param col 列坐標 
   * @param target 臨界點 
   * @private 
   */ 
  private checkPath(row: number, col: number, target: number): boolean { 
    // 兩坐標的數(shù)位之和必須小于等于臨界點 
    return sumOfDigits(row) + sumOfDigits(col) <= target; 
  } 
 
// 轉(zhuǎn)字符串實現(xiàn) 
export function sumOfDigits(target: number): number { 
  let finalVal = 0; 
  const computeVal = target.toString(); 
  for (let i = 0; i < computeVal.length; i++) { 
    finalVal += Number(computeVal[i]); 
  } 
  return finalVal; 
} 
 
// 數(shù)位之和 - 模運算實現(xiàn) 
export function sumOfDigitsForModular(target: number): number { 
  let finalVal = 0; 
  while (target > 0) { 
    finalVal += Math.floor(target % 10); 
    target /= 10; 
  } 
  return finalVal; 
} 

移動機器人函數(shù)

移動機器人至指定格子實現(xiàn)代碼如下所示：

/** 
 * 開始移動機器人 
 * @param rows 矩陣總行數(shù) 
 * @param cols 矩陣總列數(shù) 
 * @param row 待進入格子的行坐標 
 * @param col 待進入格子的列坐標 
 * @param threshold 最大活動范圍 
 * @param isVisited 訪問標識矩陣 
 * @param matrix 路徑矩陣 
 * @private 
 */   
rivate startMoving( 
  rows: number, 
  cols: number, 
  row: number, 
  col: number, 
  threshold: number, 
  isVisited: Array<Array<boolean>>, 
  matrix: Array<Array<T>> 
): number { 
  // 邊界條件判斷 
  if ( 
    row >= rows || 
    row < 0 || 
    col >= cols || 
    col < 0 || 
    isVisited[row][col] || 
    !this.checkPath(row, col, threshold) 
  ) { 
    return 0; 
  } 
  // 記錄當前訪問的格子內(nèi)容 
  this.path += `${matrix[row][col]} -> `; 
  // 標識當前格子已被訪問 
  isVisited[row][col] = true; 
  // 格子訪問數(shù)量+1 
  return ( 
    1 + 
    this.startMoving(rows, cols, row + 1, col, threshold, isVisited, matrix) + 
    this.startMoving(rows, cols, row, col + 1, threshold, isVisited, matrix) + 
    this.startMoving(rows, cols, row - 1, col, threshold, isVisited, matrix) + 
    this.startMoving(rows, cols, row, col - 1, threshold, isVisited, matrix) 
  ); 
} 

主函數(shù)

最后，我們來看下主函數(shù)的實現(xiàn)，如下所示：

/** 
 * 題目： 
 * 地上有一個m行n列的方格。 
 * 一個機器人從坐標（0，0）的格子開始移動， 
 * 它每次可以向左、右、上、下移動一格，但不能進入行坐標和列坐標的數(shù)位之和大于k的格子。 
 * 例如，當k為18時，機器人能夠進入方格 （35，37），因為3+5+3+7=18。 
 * 但它不能進入方格（35，38），因為3+5+3+8=19. 請問該機器人能夠到達多少個格子？ 
 * @param matrix 矩陣 
 * @param threshold 臨界點(最大活動范圍) 
 */ 
public movingCount(matrix: Array<Array<T>>, threshold = 0): number { 
  if (threshold < 0 || matrix.length <= 0) { 
    return 0; 
  } 
  // 獲取方格的總行數(shù)與總列數(shù) 
  const rows = matrix.length; 
  const cols = matrix[0].length; 
  // 創(chuàng)建標記數(shù)組，用于標識格子是否被訪問 
  const isVisited: Array<Array<boolean>> = new Array(rows); 
  for (let i = 0; i < isVisited.length; i++) { 
    isVisited[i] = new Array(cols); 
  } 
  // 從0,0位置開始移動，計算總的移動格子數(shù)量 
  return this.startMoving(rows, cols, 0, 0, threshold, isVisited, matrix); 
} 

完整代碼請移步：Backtracking.ts#L80

編寫測試用例

接下來，我們構造一個矩陣來驗證下上述代碼能否正確執(zhí)行，如下所示：

const pathArr = [ 
  ["a", "b", "t", "g"], 
  ["c", "f", "c", "s"], 
  ["j", "d", "e", "h"] 
]; 
 
const backtracking = new Backtracking<string>(); 
const totalCount = backtracking.movingCount(pathArr, 4); 
const path = backtracking.path; 
console.log( 
  "機器人總共可走的格子總數(shù)為: ", 
  totalCount, 
  ",運動軌跡為: ", 
  path.substr(0, path.length - 3) 
); 

執(zhí)行結果如下所示：