class Solution {
public:
vector<string> printKMoves(int K) {
}
};
面试题 16.22. 兰顿蚂蚁
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
输入: 0 输出: ["R"]
示例 2:
输入: 2 输出: [ "_X", "LX" ]
示例 3:
输入: 5 输出: [ "_U", "X_", "XX" ]
说明：
K <= 100000原站题解
python3 解法, 执行用时: 224 ms, 内存消耗: 47.7 MB, 提交时间: 2022-11-30 21:16:47
class Solution:
def printKMoves(self, K):
dirs = [(0, -1), (-1, 0), (0, 1), (1, 0)]
black = set()
pos, curr_dir = (0, 0), 2
# 模拟 K 步
for i in range(K):
if pos in black:
curr_dir = (curr_dir - 1) % 4
black.remove(pos)
else:
curr_dir = (curr_dir + 1) % 4
black.add(pos)
pos = (pos[0] + dirs[curr_dir][0], pos[1] + dirs[curr_dir][1])
all_x = [x for x, _ in black] + [pos[0]]
all_y = [y for _, y in black] + [pos[1]]
min_x, max_x, min_y, max_y = min(all_x), max(all_x), min(all_y), max(all_y)
# 初始化矩阵为全白
matrix = [["_" for _ in range(min_y, max_y + 1)] for _ in range(min_x, max_x + 1)]
# 填充黑色
for x, y in black:
matrix[x - min_x][y - min_y] = "X"
# 填充方向
matrix[pos[0] - min_x][pos[1] - min_y] = ["L", "U", "R", "D"][curr_dir]
for i in range(len(matrix)):
matrix[i] = "".join(matrix[i])
return matrix
javascript 解法, 执行用时: 336 ms, 内存消耗: 84.3 MB, 提交时间: 2022-11-30 21:15:52
class Position {
constructor(x, y) {
this.x = x
this.y = y
}
}
/**
* @param {number} K
* @return {string[]}
*/
var printKMoves = function (K) {
const direction = ['L', 'U', 'R', 'D']
const offset = [
[-1, 0],
[0, -1],
[1, 0],
[0, 1]
]
const antPos = new Position(0, 0)
let antDir = 2
const blackSet = new Set()
while (K > 0) {
const t = antPos.x + '&' + antPos.y
if (!blackSet.has(t)) {
blackSet.add(t)
antDir = (antDir + 1) % 4
} else {
antDir = (antDir + 3) % 4
blackSet.delete(t)
}
antPos.x += offset[antDir][0]
antPos.y += offset[antDir][1]
K--
}
let left = antPos.x
let top = antPos.y
let right = antPos.x
let bottom = antPos.y
for (const pos of blackSet) {
const [x, y] = pos.split('&')
left = Math.min(left, x)
top = Math.min(top, y)
right = Math.max(right, x)
bottom = Math.max(bottom, y)
}
const grid = Array(bottom - top + 1)
.fill(0)
.map(() => Array(right - left + 1).fill('_'))
for (const pos of blackSet) {
const [x, y] = pos.split('&')
grid[y - top][x - left] = 'X'
}
grid[antPos.y - top][antPos.x - left] = direction[antDir]
return grid.map((row) => row.join(''))
}
python3 解法, 执行用时: 1452 ms, 内存消耗: 32.8 MB, 提交时间: 2022-11-30 21:15:11
from typing import List
class Solution:
def printKMoves(self, K: int) -> List[str]:
white, black = "_", "X" # 白色用“_”表示，黑色用“X”表示
ant = Ant() # 实例化一只蚂蚁
board = Board(white=white, black=black) # 实例化一个网格
for _ in range(K): # 重复K次
color = board.get_color(ant.location) # 获取网格中蚂蚁所在位置处的颜色
if color == white: # 如果是白色
ant.turn_right() # 蚂蚁需要右转
elif color == black: # 如果是黑色
ant.turn_left() # 蚂蚁需要左转
else: # 非法颜色
raise Exception(color) # 提示报错
board.change_color(ant.location) # 翻转蚂蚁所在位置颜色
ant.step() # 蚂蚁向前一步走
board.set_color(ant.location, ant.current_direction) # 最后，要把蚂蚁所在位置处的颜色设置成蚂蚁的当前方向
ans = board.get_ans # 根据网格中记录的蚂蚁足迹获取最终结果
return ans # 返回结果
class Ant: # 定义一只蚂蚁
def __init__(self): # 蚂蚁的初始化
self.location = (0, 0) # 位置属性：初始化为原点
self.direction = (0, 1) # 方向属性：初始化为向右
@staticmethod
def matmul(vector, mat): # 实现向量乘以矩阵，因为向量乘以矩阵可以实现旋转
dh, dw = vector
[[a, b], [c, d]] = mat
return dh * a + dw * c, dh * b + dw * d
def turn_left(self): # 当前方向左转，需要将当前方向乘以左转矩阵
self.direction = self.matmul(self.direction, [[0, 1], [-1, 0]])
def turn_right(self): # 当前方向右转，需要将当前方向乘以右转矩阵
self.direction = self.matmul(self.direction, [[0, -1], [1, 0]])
def step(self): # 基于当前的方向，向前一步走
self.location = (self.location[0] + self.direction[0], self.location[1] + self.direction[1])
@property
def current_direction(self): # 获取当前方向的字母表示
d = {(0, 1): "R", # 右
(0, -1): "L", # 左
(1, 0): "D", # 下
(-1, 0): "U", # 上
}
return d[self.direction] # 索引查找
class Board: # 定义一个网格
def __init__(self, white="_", black="X"): # 网格的初始化函数
self.footprint = dict() # 蚂蚁在网格上留下的足迹，即每个位置点及其对应的颜色，默认颜色是白色
self.white = white # 白色默认用“_”表示
self.black = black # 黑色默认用“X”表示
self.top = 0 # 网格的上边界
self.left = 0 # 网格的左边界
self.bottom = 0 # 网格的下边界
self.right = 0 # 网格的右边界
def get_color(self, pos): # 获取某个位置处网格颜色，默认颜色为白色
return self.footprint.get(pos, self.white)
def set_color(self, pos, color): # 设置网格某个位置pos处颜色为color
self.footprint[pos] = color
self.update_border(pos) # 每次设置pos处颜色，需要根据pos更新一下边界
def change_color(self, pos): # 翻转网格的颜色
color = self.get_color(pos) # 当前颜色，非黑即白，否则报错
if color == self.white: # 如果当前位置pos处颜色是白色
self.set_color(pos, self.black) # 设置当前位置pos处颜色为黑色
elif color == self.black: # 如果当前位置pos处颜色为黑色
self.set_color(pos, self.white) # 设置当前位置pos处颜色为白色
else: # 如果是其他颜色
raise Exception(color) # 则会报错
def update_border(self, pos): # 更新网格边界
h, w = pos # pos处的h和w坐标
self.top = min(self.top, h) # 更新上边界
self.bottom = max(self.bottom, h) # 更新下边界
self.left = min(self.left, w) # 更新左边界
self.right = max(self.right, w) # 更新右边界
@property
def get_ans(self): # 根据足迹获取结果
ans = [] # 结果列表
for h in range(self.top, self.bottom + 1): # 逐行研究
line = "" # 当前行结果
for w in range(self.left, self.right + 1): # 逐列研究
line += self.get_color((h, w)) # 获取当前位置(h, w)结果
ans.append(line)
return ans
golang 解法, 执行用时: 196 ms, 内存消耗: 17.4 MB, 提交时间: 2022-11-30 21:13:57
func printKMoves(K int) []string {
dirs := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 四个方向依次为右、下、左、上
curDir := 0 // 当前方向
colors := make(map[Point]int) // 0 白色，1 黑色
edges := make([]int, 4) // 四个边界依次为最左侧、最上方、最右侧、最下方
dirChar := []byte{'R', 'D', 'L', 'U'} // 用于将更新结果数组
curPos := Point{}
for i := 0; i < K; i++ {
if colors[curPos] == 0 { // 顺时针
curDir = (curDir + 1) % 4
} else { // 逆时针
curDir = (curDir + 3) % 4
}
colors[curPos] ^= 1 // 变色
curPos = Point{curPos.x + dirs[curDir][0], curPos.y + dirs[curDir][1]} // 前进一步
updateEdge(edges, curPos) // 更新顶点
}
rows, cols := edges[3] - edges[1] + 1, edges[2] - edges[0] + 1
res := make([]string, rows)
for i := edges[1]; i <= edges[3]; i++ {
row := make([]byte, cols)
for j := edges[0]; j <= edges[2]; j++ {
color := byte('_')
if colors[Point{i,j}] == 1 {
color = byte('X')
}
row[j-edges[0]] = color
if i == curPos.x && j == curPos.y { // 填充最终位置
row[j-edges[0]] = dirChar[curDir]
}
}
res[i-edges[1]] = string(row)
}
return res
}
func updateEdge(edges []int, pos Point) {
edges[0] = min(edges[0], pos.y)
edges[1] = min(edges[1], pos.x)
edges[2] = max(edges[2], pos.y)
edges[3] = max(edges[3], pos.x)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
type Point struct {
x, y int
}