生成ascii-art非相交路径。

Question

给定两个表示字段大小的整数输入，x和y通过字段输出路径。

5, 4的示例输出：

#    
#    
# ###
### #

整个字段为5乘4，有一条由哈希标记组成的穿越字段的路径。

路径应该总是从左上角开始，然后转到右下角。每次程序运行时，整个路径都应该被随机化。每条有效的路径都应该是可能的输出。

路径的规则是：

• 由哈希标记制成
• 每个散列只连接到另外两个散列(即路径不相交，也不与自己一起运行)。

非散列空间可以用任何其他字符填充，但它必须是一致的(即所有空格、所有句点等等)。

示例：

2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

## ###
 # # #
## # #
# ## #
###  #

7, 9

#######
      #
####  #
#  #  #
#  #  #
#  #  #
#  ####
#
#######

这种路径类似于一个自我避免的随机游动，但是它不可能与自己相邻，不像一个真正的锯子。

路径连续性和路径接触都是无对角定义的。

Answer 1

QBasic，259个字节

我很喜欢GOTOs。

RANDOMIZE TIMER
INPUT w,h
DO
CLS
x=1
y=1
REDIM a(w+3,h+3)
2a(x+1,y+1)=1
LOCATE y,x
?"#"
d=INT(RND*4)
m=1AND d
x=x+m*(d-2)
y=y-d*m+m+d-1
c=a(x,y+1)+a(x+2,y+1)+a(x+1,y)+a(x+1,y+2)=1
IF(x=w)*c*(y=h)GOTO 9
IF(x*y-1)*x*y*c*(x<=w)*(y<=h)GOTO 2
LOOP
9LOCATE y,x
?"#"

基本策略:在每一步，打印一个#到当前位置，并向一个随机的方向移动。一个由0和1组成的数组a会跟踪我们去过的地方。如果移动是合法的，并带我们到端点，GOTO 9退出循环并打印最终的#。否则，如果此举是合法的，那就再走一步。否则，清除屏幕并重新开始(这比编写回溯算法要多得多！)

在我的笔记本电脑上用QB64进行测试，这通常会在5秒或更短的时间内为9, 9生成一个结果。运行10, 10的时间在3到45秒之间。从理论上讲，所有合法路径都有非零概率，但具有大曲线的路径的概率却非常小。不过，我偶尔也会看到有一两条小曲线的小径：

非高尔夫版本和/或深度解释可根据要求提供。