我走了与 @Ben 不同的路线。
我想看到路线,所以我还添加了两个额外的函数。第一个是
colorPrint
,它给矩阵中的“3”添加颜色。第二个是
directedPrint
,它将“3”替换为指向行进方向的箭头。
这两个函数中的大部分代码都是用来重新构建矩阵的“外观”。(
cat
会打印一个由数字组成的单个字符串的矩阵)
每次找到
'2'
时,这些函数都会在
search
中调用。
library(crayon)
library(tidyverse)
colorPrint <- function(mazish) {
cols <- ncol(mazish)
rows <- nrow(mazish)
mazish <- gsub(", ", " ",
lapply(1:rows,
function(k) {
toString(mazish[k, ])
}) %>% unlist()
) %>% gsub(pattern = "3", replacement = green("3"))
rowing <- paste0("[", 1:rows, ",]")
coling <- paste0("[,", 1:cols, "]")
cat(" ", coling, "\n", paste0(rowing, " ", mazish, "\n"))
}
directedPrint <- function(mazish, directed) {
directed <- data.frame(matrix(unlist(directed), ncol = 2,
nrow = length(directed), byrow = T)) %>%
setNames(c("x", "y")) %>%
mutate(direct = case_when(
lag(x) < x | lead(x) > x ~ '⬇',
lag(y) < y | lead(y) > y ~ '⮕',
lag(x) > x | lead(x) < x ~ '⬆',
lag(y) > y | lead(y) < y ~ '⬅',
TRUE ~ '·'))
cols <- ncol(mazish)
rows <- nrow(mazish)
mazishD <- matrix(as.character(mazish), nrow = rows, ncol = cols)
lapply(1:nrow(directed),
function(j) {
where <-
what <- directed[j, "direct"]
mazishD[directed[j, "x"], directed[j, "y"]] <<- red(what)
})
rowing <- paste0("[", 1:rows, ",]")
coling <- paste0("[,", 1:cols, "]")
lmaz <- gsub(", ", " ",
lapply(1:rows,
function(k) {
toString(mazishD[k, ])
}) %>% unlist()) %>%
str_replace_all(" \033", paste0(" \U200A\U2006", "\033"))
rowSp <- ifelse(substr(lmaz, 1, 1) == "\033", " \U200A\U2006", " ")
cat(" ", coling, "\n", paste0(rowing, rowSp, lmaz, "\n"))
}
这是我的
搜索
函数。
search = function(maze, x, y, directions = NULL){
if(!exists("directions")) {
directions <- list()
}
directions <- append(directions, c(x, y))
if (x == 0 | y == 0) {
return(FALSE)
} else if (x > nrow(maze) | y > ncol(maze)) {
return(FALSE)
} else if (maze[x, y] == 2){
print(paste('I am in point', x, y))
colorPrint(maze)
directedPrint(maze, directions)
return(TRUE)
} else if (maze[x, y] == 1){
print(paste('wall in point', x, y))
return(FALSE)
} else if (maze[x, y] == 3){
print(paste('visited point', x, y))
return(FALSE)
}
print(paste('visited point', x, y))
maze[x, y] <- 3
if((x < nrow(maze) & search(maze, x + 1, y, directions))
| (y > 1 & search(maze, x, y - 1, directions))
| (x > 1 & search(maze, x - 1, y, directions))
| (y < ncol(maze) & search(maze, x, y + 1, directions))) {
return(TRUE)
}
return(FALSE)
}
您将使用与最初描述类似的方式。但是,我必须说,您提供的数据在前20个条目中有障碍物,这意味着迷宫搜索无处可去。
set.seed(253)
dt <- sample(c(
sample(c(rep(0, 10), c(rep(1, 4))), 49, replace = T),
2), 50, replace = F)
maze = matrix(dt, 5, 10, byrow = TRUE)
search(maze, 1, 1)
在控制台中,您将看到每个可能的路线。但是,我只展示了一条通向终点的路线。(我将其制作成图像,以便您可以看到颜色和间距。)
![enter image description here](https://istack.dev59.com/XbZgU.webp)
你可以添加收集器,这样你就可以看到循环了多少次,以及每个解决方案需要多少步骤。
这使用外部列表。以下是更新的“search”函数。如果“== 2”,则有一行新行。
search = function(maze, x, y, directions = NULL){
if(!exists("directions")) {
directions <- list()
}
directions <- append(directions, c(x, y))
if (x == 0 | y == 0) {
return(FALSE)
} else if (x > nrow(maze) | y > ncol(maze)) {
return(FALSE)
} else if (maze[x, y] == 2){
print(paste('I am in point', x, y))
colorPrint(maze)
directedPrint(maze, directions)
d[[length(d) + 1]] <<- length(directions)
return(TRUE)
} else if (maze[x, y] == 1){
print(paste('wall in point', x, y))
return(FALSE)
} else if (maze[x, y] == 3){
print(paste('visited point', x, y))
return(FALSE)
}
print(paste('visited point', x, y))
maze[x, y] <- 3
if((x < nrow(maze) & search(maze, x + 1, y, directions))
| (y > 1 & search(maze, x, y - 1, directions))
| (x > 1 & search(maze, x - 1, y, directions))
| (y < ncol(maze) & search(maze, x, y + 1, directions))) {
return(TRUE)
}
return(FALSE)
}
要使用这个,你需要在全局环境中创建一个列表。
d = list()
dt2 <- matrix(data = c(rep(0, 5), 1,
1, 1, 0, 0, 0, 1,
0, 0, 0, 1, 0, 0,
0, 1, 0, 0, 1, 0,
0, 1, 0, 0, 0, 2,
rep(0, 5), 1),
nrow = 6, ncol = 6, byrow = F)
search(dt2, 1, 1)
这返回了43种解决方案,其中最短的序列为20步,最长的为48步。
![enter image description here](https://istack.dev59.com/oKIfv.webp)
maze <<- maze
--- 这将把全局环境中search
函数之外的maze
赋值为填充有 3 的最终迷宫...这样会有效吗? - Ben