Question

面试题 16.22. 兰顿蚂蚁

English Version

题目描述

一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。

(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。

编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。

网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。

示例 1:

输入: 0
输出: ["R"]

示例 2:

输入: 2
输出:
[
  "_X",
  "LX"
]

示例 3:

输入: 5
输出:
[
  "_U",
  "X_",
  "XX"
]

说明：

• K <= 100000

解法

方法一：哈希表 + 模拟

我们使用哈希表 $black$ 来记录所有黑色方格的位置，哈希表 $dirs$ 来记录蚂蚁的四个方向。我们使用变量 $x, y$ 来记录蚂蚁的位置，使用变量 $p$ 来记录蚂蚁的方向。我们使用变量 $x1, y1, x2, y2$ 来记录所有黑色方格的最小横坐标、最小纵坐标、最大横坐标、最大纵坐标。

我们模拟蚂蚁的行走过程。如果蚂蚁所在的方格是白色的，那么蚂蚁向右转 $90$ 度，将方格涂黑，向前移动一个单位。如果蚂蚁所在的方格是黑色的，那么蚂蚁向左转 $90$ 度，将方格涂白，向前移动一个单位。在模拟的过程中，我们不断更新 $x1, y1, x2, y2$ 的值，使得它们能够包含蚂蚁走过的所有方格。

模拟结束后，我们根据 $x1, y1, x2, y2$ 的值，构造出答案矩阵 $g$。然后，我们将蚂蚁所在的位置涂上蚂蚁的方向，同时将所有黑色方格涂上 $X$，最后返回答案矩阵。

时间复杂度 $O(K)$，空间复杂度 $O(K)$。其中 $K$ 是蚂蚁行走的步数。

class Solution:
  def printKMoves(self, K: int) -> List[str]:
    x1 = y1 = x2 = y2 = 0
    dirs = (0, 1, 0, -1, 0)
    d = "RDLU"
    x = y = 0
    p = 0
    black = set()
    for _ in range(K):
      if (x, y) in black:
        black.remove((x, y))
        p = (p + 3) % 4
      else:
        black.add((x, y))
        p = (p + 1) % 4
      x += dirs[p]
      y += dirs[p + 1]
      x1 = min(x1, x)
      y1 = min(y1, y)
      x2 = max(x2, x)
      y2 = max(y2, y)
    m, n = x2 - x1 + 1, y2 - y1 + 1
    g = [["_"] * n for _ in range(m)]
    for i, j in black:
      g[i - x1][j - y1] = "X"
    g[x - x1][y - y1] = d[p]
    return ["".join(row) for row in g]

class Solution {
  public List<String> printKMoves(int K) {
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    int[] dirs = {0, 1, 0, -1, 0};
    String d = "RDLU";
    int x = 0, y = 0, p = 0;
    Set<List<Integer>> black = new HashSet<>();
    while (K-- > 0) {
      List<Integer> t = List.of(x, y);
      if (black.add(t)) {
        p = (p + 1) % 4;
      } else {
        black.remove(t);
        p = (p + 3) % 4;
      }
      x += dirs[p];
      y += dirs[p + 1];
      x1 = Math.min(x1, x);
      y1 = Math.min(y1, y);
      x2 = Math.max(x2, x);
      y2 = Math.max(y2, y);
    }
    int m = x2 - x1 + 1;
    int n = y2 - y1 + 1;
    char[][] g = new char[m][n];
    for (char[] row : g) {
      Arrays.fill(row, '_');
    }
    for (List<Integer> t : black) {
      int i = t.get(0) - x1;
      int j = t.get(1) - y1;
      g[i][j] = 'X';
    }
    g[x - x1][y - y1] = d.charAt(p);
    List<String> ans = new ArrayList<>();
    for (char[] row : g) {
      ans.add(String.valueOf(row));
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> printKMoves(int K) {
    int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
    int dirs[5] = {0, 1, 0, -1, 0};
    string d = "RDLU";
    int x = 0, y = 0, p = 0;
    set<pair<int, int>> black;
    while (K--) {
      auto t = make_pair(x, y);
      if (black.count(t)) {
        black.erase(t);
        p = (p + 3) % 4;
      } else {
        black.insert(t);
        p = (p + 1) % 4;
      }
      x += dirs[p];
      y += dirs[p + 1];
      x1 = min(x1, x);
      y1 = min(y1, y);
      x2 = max(x2, x);
      y2 = max(y2, y);
    }
    int m = x2 - x1 + 1, n = y2 - y1 + 1;
    vector<string> g(m, string(n, '_'));
    for (auto& [i, j] : black) {
      g[i - x1][j - y1] = 'X';
    }
    g[x - x1][y - y1] = d[p];
    return g;
  }
};

func printKMoves(K int) []string {
  var x1, y1, x2, y2, x, y, p int
  dirs := [5]int{0, 1, 0, -1, 0}
  d := "RDLU"
  type pair struct{ x, y int }
  black := map[pair]bool{}
  for K > 0 {
    t := pair{x, y}
    if black[t] {
      delete(black, t)
      p = (p + 3) % 4
    } else {
      black[t] = true
      p = (p + 1) % 4
    }
    x += dirs[p]
    y += dirs[p+1]
    x1 = min(x1, x)
    y1 = min(y1, y)
    x2 = max(x2, x)
    y2 = max(y2, y)
    K--
  }
  m, n := x2-x1+1, y2-y1+1
  g := make([][]byte, m)
  for i := range g {
    g[i] = make([]byte, n)
    for j := range g[i] {
      g[i][j] = '_'
    }
  }
  for t := range black {
    i, j := t.x-x1, t.y-y1
    g[i][j] = 'X'
  }
  g[x-x1][y-y1] = d[p]
  ans := make([]string, m)
  for i := range ans {
    ans[i] = string(g[i])
  }
  return ans
}