[LeetCodeやるお]489. Robot Room Cleaner

みんな大好きLeetCodeやるお。とは言っても自分が学習したメモになります。今回はRecursion（再帰）のテーマから、BackTracking法を使う問題でした。ヒョエー！

参考：https://leetcode.com/problems/robot-room-cleaner/

グリッドでモデル化された部屋にロボットクリーナーがあるとします。
グリッドの各セルは空であったり、障害物があります。
与えられた4つのAPIを持つロボットクリーナーは、前進、左折、右折をすることができます。各々の回転は90度です。
ブロックされたセルに移動しようとすると，センサが障害物を検出し，現在のセルに留まります。
以下に示す4つの与えられたAPIだけを使って、部屋全体を掃除するアルゴリズムを設計してください。

interface Robot {
// 次のセルが移動可能で、ロボットがそのセルに移動した場合はtrueを返します。
// 次のセルが障害物で、ロボットが現在のセルに留まっている場合は、falseを返します。
boolean move();

// ロボットはturnLeft/turnRightを呼び出した後も同じセルに留まります。
// それぞれのターンは90度になります。
void turnLeft();
void turnRight();

// 現在のセルを掃除します。
void clean();
}

=============

Input:
room = [
[1,1,1,1,1,0,1,1],
[1,1,1,1,1,0,1,1],
[1,0,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0],
[1,1,1,1,1,1,1,1] ],
row = 1,
col = 3

説明:
部屋の中のすべてのグリッドには、0か1のマークがついています。
0はそのセルが塞がれていることを意味し、1はそのセルがアクセス可能であることを意味します。
ロボットは最初、row=1, col=3の位置からスタートします。
左上から見て1行下、3列右の位置です。

=============
注意：
入力は、部屋とロボットの位置を内部で初期化するためだけに与えられます。あなたはこの問題を「目隠しして」解かなければなりません。
言い換えれば、部屋のレイアウトやロボットの初期位置を知らずに、前述の4つのAPIだけを使ってロボットを制御しなければなりません。
ロボットの初期位置は常にアクセス可能なセルの中にあります。
ロボットの初期方向は上向きです。
すべてのアクセス可能なセルは接続されており、1とマークされたセルはすべてロボットがアクセス可能です。
グリッドの4つのエッジがすべて壁で囲まれていると仮定します。

アプローチ

押さえておかなければいけないのは、

ということですね。

この問題は深さ優先探索（Depth First Search）、つまりこれ以上進めなくなるところまで行ったら、戻って別のノードを検索するというやり方を用います。

また通常の”ソフトウェア”の問題であればrecursionを用いて元の場所に戻るには、retrunをするだけで良いのですが、今回はロボットの物理的な移動を考慮する必要があります。、つまり

という処理を用いて、元の場所に戻す必要があるということです。

例えばロボットが①→②という感じで左の①から右の②へ移動した後、同じ場所（①）に戻る（①の場所に戻ってやり直す場合は）

というステップを踏まなければなりません。というわけで問題に入っていきます、

保持するパラメーターは以下を設定します。

・ロボットの向き
・X座標
・y座標

また配列を用意して、現在の位置から上に進むなら「−１、０」、右に進むなら、「０、１」、下なら「１、０」左なら「０、−１」と定義しておきます。時計回りで、上、右、下、左の順番を設けます。

初回の位置を０、０とし、訪れた場所についてはHashSetに値を保管して掃除(clean)をします。（HashSetはvisitedと名付けます）

次に移動する場所が、visitedに含まれておらず、障害物がない場合、（move()がtrue）の場合、再帰をおこないます。

現在の位置から４方向に対して、visitedに含まれているか、または障害物で動けない場合は、元の呼び出しもとに戻って向きを変えます。

スポンサーリンク

実装

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     public boolean move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     public void turnLeft();
 *     public void turnRight();
 *
 *     // Clean the current cell.
 *     public void clean();
 * }
 */

class Solution {
  // going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
  int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  Set<Pair<Integer, Integer>> visited = new HashSet();
  Robot robot;

  public void goBack() {
    robot.turnRight();
    robot.turnRight();
    robot.move();
    robot.turnRight();
    robot.turnRight();
  }

  public void backtrack(int row, int col, int d) {
    visited.add(new Pair(row, col));
    robot.clean();
    // going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
    for (int i = 0; i < 4; ++i) {
//値を常に０、１、２、３のいずれかに設定する
      int newD = (d + i) % 4;
      int newRow = row + directions[newD][0];
      int newCol = col + directions[newD][1];

      if (!visited.contains(new Pair(newRow, newCol)) && robot.move()) {
        backtrack(newRow, newCol, newD);
        goBack();
      }
      // turn the robot following chosen direction : clockwise
      robot.turnRight();
    }
  }

  public void cleanRoom(Robot robot) {
    this.robot = robot;
    backtrack(0, 0, 0);
  }
}