Pythonで解く：訪問済みマスをスキップして移動するロボットが目標座標に到達するかを判定するプログラム

問題の概要

直交座標平面上の原点 (0, 0) にロボットが置かれているとします。このロボットには、N（北）、S（南）、W（西）、E（東）の4種類の移動命令からなるリストが与えられます。ただし、次の特殊なルールがあります。すでに訪れたことのある地点に到達した場合、ロボットは未訪問の地点に到達するまで同じ方向へ移動し続けるというものです。

このルールのもとですべての移動を実行したあと、ロボットが指定された座標 (x, y) に到達しているかどうかを判定するのが、この記事で扱う課題です。

入力例と動作の確認

たとえば、次のような入力を考えてみましょう。

moves = ['N', 'N', 'E', 'N', 'W', 'S']
coord = [0, -1]

この場合の出力は True になります。ロボットはまず2回上へ移動し、次に1回右へ、さらに1回上へ、そして1回左へと進みます。ここから下（南）へ移動しようとすると、直後の地点がすでに訪問済みであるため、そのまま下へ進み続けます。訪問済みの地点 (0, 2)、(0, 1)、(0, 0) を順に通過し、最終的に未訪問の地点 (0, -1) で停止します。これが目標座標と一致するため、結果は True となるのです。

解法のアプローチ

この問題は、訪問済みの座標を集合（set）で管理することでシンプルに解けます。手順は以下の通りです。

• 現在位置を nx := 0、ny := 0 で初期化します。
• 訪問済み地点を格納する新しい集合 l を用意し、最初に (0, 0) を挿入しておきます。
• moves 内の各命令 k に対して、次の処理を行います。
  • k が「N」の場合：(nx, ny) が集合 l に含まれる間、ny を 1 ずつ増やします。
  • k が「S」の場合：(nx, ny) が集合 l に含まれる間、ny を 1 ずつ減らします。
  • k が「E」の場合：(nx, ny) が集合 l に含まれる間、nx を 1 ずつ増やします。
  • それ以外（W）の場合：(nx, ny) が集合 l に含まれる間、nx を 1 ずつ減らします。
  • 最終的な (nx, ny) を集合 l に追加します。
• すべての移動が終わったら、coord が (nx, ny) と一致すれば true、そうでなければ false を返します。

ポイントは、直前の停止地点が必ず集合へ登録されているため、while ループは最低でも1回実行され、ロボットが必ず1歩以上進むようになっている点です。その後も訪問済みのマスが続く限り、同じ方向へまるでスキップするように進み続けます。

Pythonでの実装例

それでは、理解を深めるために実際のコードを見ていきましょう。

class Solution:
    def solve(self, moves, coord):
        ny = nx = 0
        l = {(0, 0)}
        for k in moves:
            if k == 'N':
                while (nx, ny) in l:
                    ny += 1
            elif k == 'S':
                while (nx, ny) in l:
                    ny -= 1
            elif k == 'E':
                while (nx, ny) in l:
                    nx += 1
            else:
                while (nx, ny) in l:
                    nx -= 1
            l.add((nx, ny))
        return coord[0] == nx and coord[1] == ny

ob = Solution()
moves = ['N', 'N', 'E', 'N', 'W', 'S']
coord = [0, -1]
print(ob.solve(moves, coord))

入力

['N', 'N', 'E', 'N', 'W', 'S'], [0, -1]

出力

True

計算量の目安

移動命令ごとに必ず1つの停止地点が集合へ追加されるため、集合のサイズは命令の数に比例して増加します。実行時間については、命令の数に加えて、訪問済みマスをスキップした合計ステップ数にも依存します。それでも、Pythonの set による存在チェックが高速に行えるおかげで、全体として非常に効率的な実装になっています。