バックトラッキングアルゴリズム - ロボットの動作範囲

[[415476]]

この記事はWeChatの公開アカウント「Magic Programmer K」から転載したもので、著者はMagic Programmer Kです。この記事を転載する場合は、マジカルプログラマーKの公開アカウントまでご連絡ください。

序文

行列があります。ロボットは座標 (0,0) のグリッドから移動を開始できます。ロボットは一度に 1 つのグリッドを左、右、上、または下に移動できますが、行と列の座標の合計が K より大きいグリッドには入ることができません。ロボットが移動できるグリッドの合計数と移動軌跡を求めます。

この記事では、この問題の解決策を紹介します。興味のある開発者は、ぜひこの記事をお読みください。

実装のアイデア

マトリックス内のパスの検索に関する前回の記事では、バックトラッキングアルゴリズムを使用してマトリックス内のグリッドにアクセスする方法を学びました。この記事で説明する問題は、グリッドにアクセスする前に判断のレイヤーを作成します。条件が満たされている場合は入力できますが、そうでない場合は入力できません。

私たちが下すべき判断は、訪問するグリッドの座標の桁の合計を計算することです。それが K (最大アクティビティ範囲) より大きい場合、訪問できません。

桁の合計: 数値内の各位置の値の合計と値の合計。たとえば、19 の数字の合計は 1 + 9 = 10 です。

現在のグリッドが訪問されたかどうかを判定する

まず、ロボットがこのグリッドまで歩いたかどうかを示すために、元の行列と同じサイズの行列を作成する必要があります。

js では指定サイズの 2 次元配列を直接作成することはできません。作成の考え方は以下のとおりです。

行列の長さを持つ配列を作成する
作成した配列を走査し、行列の0番目の配列の長さをサイズとする配列を作成し、走査した各項目に値を割り当てます。

グリッドにアクセスできるかどうかを判断する

グリッドにアクセスするときは、アクセスするグリッドがアクセス可能かどうかを判断する必要があります。行座標と列座標の合計を計算し、それらを合計して、結果がロボットの最大動作範囲 (K) より大きいかどうかを判断する必要があります。

数字の合計を計算する方法は 2 つあります。

数字を文字列に変換し、各文字を走査して抽出し、それを数字に変換して合計します。
数値に対して剰余演算を実行し、結果を加算し、数値が0以下になるまで数値自体に対して/10演算を実行します。

ロボットを動かし始める

ロボットを動かすときには、次の 7 つのパラメータが必要です。

行列の行の総数
行列の列の総数
入力するグリッドの行座標
グリッドに入る列の座標
最大可動範囲
アクセスアイデンティティマトリックス
パスマトリックス

まず、境界条件の判定（再帰終了条件）を行う必要があります。条件が満たされた場合、グリッドにアクセスできず、トラバース可能なグリッドは 0 であることを意味します（直接 0 を返します）。

アクセスするグリッドの行座標がマトリックス内の行の総数より大きい
訪問するグリッドの行座標が0未満です
アクセスするグリッドの列座標がマトリックス内の列の総数より大きい
アクセスするグリッドの列座標が0未満です
現在のグリッドは訪問済みです
現在のグリッドには入力できません

上記の条件がすべて満たされている場合、現在のグリッドにアクセスできることを意味します。現在のグリッドの値はアクションの軌跡に保存され、現在のグリッドは訪問済みとしてマークされ、歩いたグリッドの数 + 1 になり、現在のグリッドの他の 4 方向のグリッドに入ることができるかどうかを再帰的に確認します。

再帰スタックがクリアされると、ロボットが進入できるグリッドの合計数とその移動軌跡が取得されます。

実装コード

次に、上記のアイデアを TypeScript コードに変換します。

グリッドは関数を入力できますか?

まず、現在のグリッドに入ることができるかどうかを判断する関数の実装を見てみましょう。

  /**
   * ロボットがターゲットグリッドに入ることができるかどうかを判定する
   * @param row 行座標
   * @param col 列座標
   * @param ターゲット臨界点
   * @プライベート
   */
  プライベートチェックパス(行: 数値、列: 数値、ターゲット: 数値): ブール値 {
    // 2つの座標の桁の合計は臨界点以下でなければならない
sumOfDigits(行) + sumOfDigits(列) <= ターゲットを返します。
  } 
 
 // 文字列を文字列に変換する
エクスポート関数sumOfDigits(ターゲット: 数値): 数値 {
  finalVal = 0 とします。
  定数 computeVal = target.toString();
 ( i = 0 とします; i < computeVal.length; i++) {
    finalVal += Number(computeVal[i]);
  }
 finalValを返します。
 } 
 
 // 桁の合計 - モジュロ演算の実装
エクスポート関数sumOfDigitsForModular(ターゲット: 数値): 数値 {
  finalVal = 0 とします。
  (ターゲット > 0) の間 {
    finalVal += Math.floor(ターゲット % 10);
    ターゲット /= 10;
  }
 finalValを返します。
 }

ロボット移動機能

ロボットを指定されたグリッドに移動するためのコードは次のとおりです。

 /**
 * ロボットを動かし始める
 * @param rows行列の行の総数
 * @param cols 行列の列の総数
 * @param row グリッドに入力する行座標
 * @param col グリッドに入力する列座標
 * @param しきい値最大アクティビティ範囲
 * @param isVisited 訪問識別マトリックス
 * @param 行列パス行列
 * @プライベート
 */
 rivate開始移動(
行数: 数、
  列: 番号、
  行: 番号、
  col: 番号、
  閾値: 数値、
  isVisited: 配列<配列<ブール値>>,
  行列: 配列<配列<T>>
 ）： 番号 {
  //境界条件判定
  もし （
    行 >=行||
    行 < 0 ||
    列 >= 列数 ||
    列 < 0 ||
    isVisited[行][列] ||
    !this.checkPath(行、列、しきい値)
  ）{
 0を返します。
  }
  //現在訪問しているグリッドの内容を記録する
  this.path += `${matrix[row][col]} -> `;
  // 現在のグリッドが訪問されたことを示します
  isVisited[行][列] = true ;
  // グリッドアクセス番号 + 1
戻る（
    1 +
    this.startMoving(行数、列数、行 + 1、列数、しきい値、isVisited、行列) +
    this.startMoving(行数、列数、行、列 + 1、しきい値、isVisited、行列) +
    this.startMoving(行数、列数、行 - 1、列数、しきい値、isVisited、行列) +
    this.startMoving(行数、列数、行、列 - 1、しきい値、isVisited、行列)
  );
 }

主な機能

最後に、以下に示すように、メイン関数の実装を見てみましょう。

 /**
 * タイトル：
 * 地面には m 行 n 列の正方形のグリッドがあります。
 * ロボットは座標(0, 0)のグリッドから移動を開始します。
 * 一度に 1 つのグリッドを左、右、上、または下に移動できますが、行と列の数字の合計が k より大きいグリッドには入ることができません。
 * たとえば、k が 18 の場合、3+5+3+7=18 なので、ロボットは (35, 37) のマスに入ることができます。
 * しかし、3+5+3+8=19 なので、(35, 38) のマスに入ることはできません。ロボットはいくつのマスまで到達できるでしょうか?
 * @param 行列 行列
 * @param 閾値臨界点（最大活動範囲）
 */
パブリック移動カウント(行列: Array<Array<T>>, しきい値 = 0): 数値 {
  閾値<0 || 行列の長さ<=0の場合{
 0を返します。
  }
  // グリッドの行と列の合計数を取得します
  定数行= 行列の長さ;
  定数列 = 行列[0].長さ;
  // グリッドが訪問されたかどうかを示すマーカー配列を作成します
  const isVisited: Array<Array<boolean>> = new Array( rows );
 ( i = 0 とします; i < isVisited.length; i++) {
    isVisited[i] = 新しい配列(cols);
  }
  // 位置 0,0 から移動を開始し、移動するグリッドの総数を計算します
this.startMoving(行数、列数、0、0、しきい値、isVisited、行列 )を返します。
 }

完全なコードについては、Backtracking.ts#L80 をご覧ください。

テストケースの作成

次に、上記のコードが正しく実行できるかどうかを確認するために、以下に示すように行列を作成します。

定数pathArr = [
  [ "a" 、 "b" 、 "t" 、 "g" ],
  [ "c" 、 "f" 、 "c" 、 "s" ],
  [ "j" 、 "d" 、 "e" 、 "h" ]
 ]; 
 
 const バックトラッキング = new Backtracking<string>();
 const totalCount = backtracking.movingCount(pathArr, 4);
定数 path = バックトラッキング.path;
コンソール.log(
 「ロボットが移動できるグリッドの合計数は次のとおりです:」 、
  合計数、
 "、動作の軌跡は次のようになります: " 、
  パス.substr(0, パス.長さ - 3)
 );