返回介绍

lcci / 16.22.Langtons Ant / README_EN

发布于 2024-06-17 01:04:42 字数 6934 浏览 0 评论 0 收藏 0

16.22. Langtons Ant

中文文档

Description

An ant is sitting on an infinite grid of white and black squares. It initially faces right. All squares are white initially.

At each step, it does the following:

(1) At a white square, flip the color of the square, turn 90 degrees right (clockwise), and move forward one unit.

(2) At a black square, flip the color of the square, turn 90 degrees left (counter-clockwise), and move forward one unit.

Write a program to simulate the first K moves that the ant makes and print the final board as a grid.

The grid should be represented as an array of strings, where each element represents one row in the grid. The black square is represented as 'X', and the white square is represented as '_', the square which is occupied by the ant is represented as 'L', 'U', 'R', 'D', which means the left, up, right and down orientations respectively. You only need to return the minimum matrix that is able to contain all squares that are passed through by the ant.

Example 1:


Input: 0

Output: ["R"]

Example 2:


Input: 2

Output:

[

  "\_X",

  "LX"

]

Example 3:


Input: 5

Output:

[

  "\_U",

  "X\_",

  "XX"

]

Note:

  • K <= 100000

Solutions

Solution 1: Hash Table + Simulation

We use a hash table $black$ to record the positions of all black squares, and a hash table $dirs$ to record the four directions of the ant. We use variables $x, y$ to record the position of the ant, and variable $p$ to record the direction of the ant. We use variables $x1, y1, x2, y2$ to record the minimum horizontal coordinate, minimum vertical coordinate, maximum horizontal coordinate, and maximum vertical coordinate of all black squares.

We simulate the ant's walking process. If the square where the ant is located is white, the ant turns right by $90$ degrees, paints the square black, and moves forward one unit. If the square where the ant is located is black, the ant turns left by $90$ degrees, paints the square white, and moves forward one unit. During the simulation, we continuously update the values of $x1, y1, x2, y2$ so that they can contain all the squares the ant has walked through.

After the simulation is over, we construct the answer matrix $g$ based on the values of $x1, y1, x2, y2$. Then, we paint the direction of the ant on the square where the ant is located, paint all black squares with $X$, and finally return the answer matrix.

The time complexity is $O(K)$, and the space complexity is $O(K)$. Here, $K$ is the number of steps the ant walks.

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
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文