矩陣路徑深度搜索

yexiaobai 發布于2019-06-27 15:22 / 525人閱讀

摘要：現用點的標記數字組成的序列來表示這樣的矩陣路徑，例如是矩陣中的一條路徑，而就不是。判定輸入的序列是否表示了一個合規的矩陣路徑，若是，返回，若不是，返回。

情景

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。

云服務器 GPU云服務器服務器路徑搜索功能深度優先搜索深度搜索距離java 投影矩陣

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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