矩阵路径深度搜索

yexiaobai 发布于2019-06-27 15:22 / 339人阅读

摘要：现用点的标记数字组成的序列来表示这样的矩阵路径，例如是矩阵中的一条路径，而就不是。判定输入的序列是否表示了一个合规的矩阵路径，若是，返回，若不是，返回。

情景

coding.net为了活跃气氛，春节期间出了一个鸡年猴语言的娱乐coding，2月2号的谜题是矩阵路径 [path_in_matrix]算法。

#鸡年猴语言#
矩阵路径是这样一个点序列：从给定矩阵中任一数字标记的点出发，每一步可以向左、右、上、下四个方向之一移动一格到达下一个点，依次类推而得到的点序列，一条矩阵路径最少包含两个点，同一个点可以多次出现在一条矩阵路径上。现用点的标记数字组成的序列来表示这样的矩阵路径，例如 1 5 6 7 是矩阵中的一条路径，而 8 5 1 4 就不是。判定输入的序列是否表示了一个合规的矩阵路径，若是，输出 1，若不是，输出 0。input 会给出多组序列，每组中间用 0 做分隔符。

给定的矩阵如下：
1 2 3 4
5 6 7 8
1 4 2 6
3 5 1 7

参与方式：在冒泡话题 #鸡年猴语言# 下首行添加题目注释，像这样：
#鸡年猴语言#
//[path_in_matrix]

勤劳的自动检测机器人 @monkey_worker 就会运行你的程序并且将输出值和是否成功评论在你的冒泡下方。
了解更多游戏规则及猴语言语法
Tips：如何从 input 读取数值呢？参考这些代码

实现

算法其实就是矩阵的深度搜索，但是同一节点可以多次出现在同一条路径中。

PHP实现：

= count($matrix) || $cols < 0 || $cols >= count($matrix[0]) || $start < 0) {
        return false;
    }
    
    if ($start == count($str)) {
        return true;
    }
    if ($matrix[$rows][$cols] === $str[$start]) {
        return dfs($matrix, $rows, $cols + 1, $start + 1, $str) ||
            dfs($matrix, $rows, $cols - 1, $start + 1, $str) ||
            dfs($matrix, $rows + 1, $cols, $start + 1, $str) ||
            dfs($matrix, $rows - 1, $cols, $start + 1, $str);
    }
    return false;
}

$matrix = [
    [1,2,3,4],
    [5,6,7,8],
    [1,4,2,6],
    [3,5,1,7]
];
$str = [1,5,6,4];
$str = [3,7,8,6,7,1];
$str = [2,1,5,8,6];
var_dump(hasPath($matrix, $str));

上面三条路打印结果分别为:true true false。

服务器托管云服务器服务器路径搜索功能深度优先搜索深度搜索距离java 投影矩阵

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/22312.html

学习JavaScript数据结构与算法 — 图

摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。定义图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和...

yiliang 2019-08-22 11:09 评论0 收藏0
[Algo] Longest Descending Path 滑雪问题

摘要：代码一个全局矩阵记录每个点能开始的最长路径对每个点开始深度优先搜索看是否有必要更新全局最大长度如果已经计算过，则直接返回递归上下左右 Longest Descending Path 给出一个矩阵，求矩阵中从某个点开始，最长的下降路径。路径可以走上下左右四个方向。求最长路径的长度。 1 2 3 4 5 6 7 8 其中一条最长路径是8 7 6 5 1 记忆化搜索复杂度时间 O(...

ybak 2019-08-14 12:47 评论0 收藏0
用JavaScript实现图的广度优先和深度优先遍历

摘要：图的相关术语有一条边相连的顶点叫相邻顶点一个顶点的度就是该顶点的相邻顶点数路径指顶点组成的连续序列简单路径没有重复顶点有向图和无向图图的表示邻接矩阵代表节点和节点相邻，否则不相邻邻接表相当于把每个节点的相邻节点一一列举出来。 1.图的相关术语 1.1.有一条边相连的顶点叫相邻顶点；1.2.一个顶点的度就是该顶点的相邻顶点数；1.3.路径指顶点组成的连续序列；1.4.简单路径没有重复顶点...

Hydrogen 2019-08-23 17:11 评论0 收藏0
Javascript的数据结构与算法(三)

摘要：存在好几种方式来表示这种数据结构。下面的示意图展示了邻接表数据结构。在关联矩阵中矩阵的行表示顶点列表示边。广度优先搜索算法和深度优先搜索算法基本上是相同的只有一点不同那就是待访问顶点列表的数据结构。 1 树一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作...

MasonEast 2019-08-21 11:24 评论0 收藏0
采用矩阵+深度优先算法解决迷宫问题

摘要：所谓深度优先算法，百科的解答是这样的深度优先搜索算法，简称是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。这一过程一直进行到已发现从源节点可达的所有节点为止。所谓深度优先算法，百科的解答是这样的深度优先搜索算法（Depth-First-Search），简称DFS,是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过...

yankeys 2019-08-20 13:54 评论0 收藏0