javascript – 用单一路径填充2D网格
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了javascript – 用单一路径填充2D网格，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4078字，纯文字阅读大概需要6分钟。
内容图文
如何用数字填充方形二维数组,以便从1到(边长)2创建一个按升序排列的连续数字的(随机)路径？
我正在尝试用JavaScript编写一个Hidato(又名Hidoku)生成器.它不一定是最好的语言,但这就是我目前正在使用的语言.游戏板最初只是部分填充.显示的唯一保证数字是路径中的第一个和最后一个数字.游戏的想法是通过网格(垂直,水平或对角)创建单个数字路径,以便有一个连续的上升数字链.由于考虑了对角线,链条可以重叠.
我被困在板子生成部分.有效网格必须具有从1到(网格大小)2的连续数字(单个非分支)路径.我看了看,但发现没什么可能帮助的.是否存在路径跟踪算法,可以使用由连续数字组成的单个路径填充2D阵列？
我最初的,天真的方法是用值和交换值填充2D数组,直到网格是有效的Hidato拼图.这需要永远计算并且效率非常低,所以我废弃了这个想法.
我的下一个想法是使用回溯路径跟踪器用连续值填充网格,但是我不确定如何实现这样的跟踪器.生成一个路径很容易(选择一个随机的相邻单元并移动到它直到二维数组已满),但我的问题是算法的“回溯性”,或者其他一些方法来始终确保有一个随机的整个网格中连续数字的路径.我想过一个迷宫追踪器,但这并不涉及没有分叉或死路的单一路径.
我怎么能从这里开始？我应该考虑除路径跟踪器或其他类似算法之外的其他选项吗？
相关问题：
> Routing “paths” through a rectangular array
> Algorithm to find a random Hamiltonian path in a grid?
解决方法:
事实证明,由于Angluin和Valiant(1977)的Hamilton路径的局部搜索算法在这方面相当不错,即使没有非随机图的证据.这是一个样本广场
99 98 101 103 105 106 129 132 133 140 135 136
97 100 102 104 107 130 131 128 141 134 139 137
95 96 109 108 112 122 127 126 125 142 143 138
80 94 110 111 121 113 123 124 40 39 36 144
79 81 93 120 116 115 114 48 41 38 37 35
78 82 92 90 119 117 47 46 49 42 33 34
77 83 84 91 89 118 45 58 43 50 32 31
76 1 85 87 88 60 59 44 57 51 30 28
75 2 86 4 6 63 61 54 52 56 29 27
73 74 3 7 5 64 62 53 55 22 24 26
72 69 67 8 65 11 12 14 15 23 21 25
70 71 68 66 9 10 13 16 17 18 19 20
和(有点仓促编写)Java代码.
import java.util.*;
public class AV {
public static void main(String[] args) {
// construct an n-by-n grid
int n = 12;
Node[][] node = new Node[n][n];
List<Node> nodes = new ArrayList<Node>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
nodes.add((node[i][j] = new Node()));
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i >= 1) {
if (j >= 1) {
node[i - 1][j - 1].addEdge(node[i][j]);
}
node[i - 1][j].addEdge(node[i][j]);
if (j < n - 1) {
node[i - 1][j + 1].addEdge(node[i][j]);
}
}
if (j >= 1) {
node[i][j - 1].addEdge(node[i][j]);
}
}
}
findPath(nodes);
labelPath(nodes);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%4d", node[i][j].label);
}
System.out.println();
}
}
private static void findPath(List<Node> nodes) {
for (Node node : nodes) {
node.isOnPath = false;
}
Random random = new Random();
Node sink = nodes.get(random.nextInt(nodes.size()));
sink.isOnPath = true;
int isNotOnPathCount = nodes.size() - 1;
while (isNotOnPathCount > 0) {
sink.pathOut = sink.out.get(random.nextInt(sink.out.size()));
sink = sink.pathOut.head;
if (sink.isOnPath) {
// rotate
sink = sink.pathOut.head;
Arc reverse = null;
Node node = sink;
do {
Arc temp = node.pathOut;
node.pathOut = reverse;
reverse = temp.reverse;
node = temp.head;
} while (node != sink);
} else {
// extend
sink.isOnPath = true;
isNotOnPathCount--;
}
}
}
private static void labelPath(Collection<Node> nodes) {
for (Node node : nodes) {
node.isSource = true;
}
for (Node node : nodes) {
if (node.pathOut != null) {
node.pathOut.head.isSource = false;
}
}
Node source = null;
for (Node node : nodes) {
if (node.isSource) {
source = node;
break;
}
}
int count = 0;
while (true) {
source.label = ++count;
if (source.pathOut == null) {
break;
}
source = source.pathOut.head;
}
}
}
class Node {
public final List<Arc> out = new ArrayList<Arc>();
public boolean isOnPath;
public Arc pathOut;
public boolean isSource;
public int label;
public void addEdge(Node that) {
Arc arc = new Arc(this, that);
this.out.add(arc.reverse);
that.out.add(arc);
}
}
class Arc {
public final Node head;
public final Arc reverse;
private Arc(Node head, Arc reverse) {
this.head = head;
this.reverse = reverse;
}
public Arc(Node head, Node tail) {
this.head = head;
this.reverse = new Arc(tail, this);
}
}
内容总结
以上是互联网集市为您收集整理的javascript – 用单一路径填充2D网格全部内容，希望文章能够帮你解决javascript – 用单一路径填充2D网格所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。