README.md

面试题 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
}