我的问题如下(简化):
-
我有一块板,用n x m平方的矩阵表示(n可能等于m)
-
在里面,有
p
游戏单品
-
每个游戏片段都有一个预定义的速度,即它在回合中可以走多少步
-
工件不能重叠
-
有三种类型的细胞:那些不需要额外运动才能穿越的细胞(穿越时你会失去额外的速度),那些需要额外运动就能穿越的细胞,还有一些你根本无法穿过的细胞(比如墙)
所以,给定一个特定的游戏片段
[i,j]
我想知道:
a)
它能以它的速度移动到所有的地方
b)
通往某个
[k,l]
在董事会中的位置
求解a),b)几乎是微不足道的。
目前我使用的算法如下,假设一种语言,其中数组大小为
n
从
0
到
n-1
:
-
创建一个速度*2+1大小的平方矩阵,表示移动的成本,就好像所有单元格都没有额外的成本要交叉一样(工件在位置[speed,speed]上)
-
创建另一个速度*2+1大小的正方形矩阵,该矩阵具有每个单元格的额外成本(那些不能交叉的矩阵,因为它是一面墙或其中有另一块具有无限值)(该块位于位置[speed,speed])
-
创建另一个速度*2+1大小的方阵,它是前两个的总和(工件位于位置[speed,speed])
-
更正后一个矩阵,确保每个单元格的值为:所有相邻单元格的最小成本+1+单元格的额外成本。如果不是,我会更正它,然后重新开始矩阵。
例如:
P
都是碎片,
W
是墙,
E
是无需额外移动的空单元格,
X
是需要
1.
要跨越的额外移动。
X,E,X,X,X
X,X,X,X,X
W,E,E,E,W
W,E,X,E,W
E,P,P,P,P
第一个矩阵:
2,2,2,2,2
2,1,1,1,2
2,1,0,1,2
2,1,1,1,2
2,2,2,2,2
第二个矩阵:
1,0,1,inf,1
1,1,1,1,1
inf,0,0,0,inf
inf,0,1,0,inf
0,inf,inf,inf,inf
总计:
3,2,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
自从
[0,0]
不是
2+1+1
,我更正它:
总计:
4,2,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
自从
[0,1]
不是
2+1+0
,我更正它:
总计:
4,3,3,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
自从
[0,2]
不是
2+1+1
,我更正它:
总计:
4,2,4,3,3
3,2,2,2,3
inf,1,0,1,inf
inf,1,2,1,inf
inf,inf,inf,inf,inf
哪一个是正确答案?
我想知道的是,如果这个问题有名字,我可以搜索它(找不到任何东西),或者是否有人可以告诉我如何解决这个问题
a)
.
请注意,我需要最佳解决方案,所以我使用了动态编程算法。随机漫步者可能更好吗?AFAIK,这个解决方案还没有失败,但我没有正确的证据,我想确保它能正常工作。