矩陣路徑深度搜索

yexiaobai 發(fā)布于2019-06-27 15:22 / 592人閱讀

摘要：現(xiàn)用點(diǎn)的標(biāo)記數(shù)字組成的序列來表示這樣的矩陣路徑，例如是矩陣中的一條路徑，而就不是。判定輸入的序列是否表示了一個合規(guī)的矩陣路徑，若是，返回，若不是，返回。

情景

coding.net為了活躍氣氛，春節(jié)期間出了一個雞年猴語言的娛樂coding，2月2號的謎題是矩陣路徑 [path_in_matrix]算法。

#雞年猴語言# 
矩陣路徑是這樣一個點(diǎn)序列：從給定矩陣中任一數(shù)字標(biāo)記的點(diǎn)出發(fā)，每一步可以向左、右、上、下四個方向之一移動一格到達(dá)下一個點(diǎn)，依次類推而得到的點(diǎn)序列，一條矩陣路徑最少包含兩個點(diǎn)，同一個點(diǎn)可以多次出現(xiàn)在一條矩陣路徑上?，F(xiàn)用點(diǎn)的標(biāo)記數(shù)字組成的序列來表示這樣的矩陣路徑，例如 1 5 6 7 是矩陣中的一條路徑，而 8 5 1 4 就不是。判定輸入的序列是否表示了一個合規(guī)的矩陣路徑，若是，輸出 1，若不是，輸出 0。input 會給出多組序列，每組中間用 0 做分隔符。
給定的矩陣如下：
1 2 3 4
5 6 7 8
1 4 2 6
3 5 1 7
參與方式：在冒泡話題 #雞年猴語言# 下首行添加題目注釋，像這樣：
#雞年猴語言# 
//[path_in_matrix]
勤勞的自動檢測機(jī)器人 @monkey_worker 就會運(yùn)行你的程序并且將輸出值和是否成功評論在你的冒泡下方。
了解更多游戲規(guī)則及猴語言語法
Tips：如何從 input 讀取數(shù)值呢？參考這些代碼

實(shí)現(xiàn)

算法其實(shí)就是矩陣的深度搜索，但是同一節(jié)點(diǎn)可以多次出現(xiàn)在同一條路徑中。

PHP實(shí)現(xiàn)：

= 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));

上面三條路打印結(jié)果分別為:true true false。

GPU云服務(wù)器云服務(wù)器服務(wù)器路徑搜索功能深度優(yōu)先搜索深度搜索距離java 投影矩陣

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://hztianpu.com/yun/22312.html

相關(guān)文章

學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法 — 圖

摘要：圖關(guān)聯(lián)矩陣在關(guān)聯(lián)矩陣表示的圖中，矩陣的行表示頂點(diǎn)，列表示邊。如圖，頂點(diǎn)數(shù)是，邊的數(shù)量是，用鄰接矩陣表示圖需要的空間是，而使用關(guān)聯(lián)矩陣表示圖需要的空間是。廣度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是隊列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。定義圖和散列表、二叉樹一樣，是一種非線性數(shù)據(jù)結(jié)構(gòu)。如圖1所示，圖由一系列頂點(diǎn)以及連接頂點(diǎn)的邊構(gòu)成。由一條邊連接在一起的頂點(diǎn)成為相鄰頂點(diǎn)，比如A和B、A和D是相鄰的，而A和...

yiliang 2019-08-22 11:09 評論0 收藏0
[Algo] Longest Descending Path 滑雪問題

摘要：代碼一個全局矩陣記錄每個點(diǎn)能開始的最長路徑對每個點(diǎn)開始深度優(yōu)先搜索看是否有必要更新全局最大長度如果已經(jīng)計算過，則直接返回遞歸上下左右 Longest Descending Path 給出一個矩陣，求矩陣中從某個點(diǎn)開始，最長的下降路徑。路徑可以走上下左右四個方向。求最長路徑的長度。 1 2 3 4 5 6 7 8 其中一條最長路徑是8 7 6 5 1 記憶化搜索復(fù)雜度時間 O(...

ybak 2019-08-14 12:47 評論0 收藏0
用JavaScript實(shí)現(xiàn)圖的廣度優(yōu)先和深度優(yōu)先遍歷

摘要：圖的相關(guān)術(shù)語有一條邊相連的頂點(diǎn)叫相鄰頂點(diǎn)一個頂點(diǎn)的度就是該頂點(diǎn)的相鄰頂點(diǎn)數(shù)路徑指頂點(diǎn)組成的連續(xù)序列簡單路徑?jīng)]有重復(fù)頂點(diǎn)有向圖和無向圖圖的表示鄰接矩陣代表節(jié)點(diǎn)和節(jié)點(diǎn)相鄰，否則不相鄰鄰接表相當(dāng)于把每個節(jié)點(diǎn)的相鄰節(jié)點(diǎn)一一列舉出來。 1.圖的相關(guān)術(shù)語 1.1.有一條邊相連的頂點(diǎn)叫相鄰頂點(diǎn)；1.2.一個頂點(diǎn)的度就是該頂點(diǎn)的相鄰頂點(diǎn)數(shù)；1.3.路徑指頂點(diǎn)組成的連續(xù)序列；1.4.簡單路徑?jīng)]有重復(fù)頂點(diǎn)...

Hydrogen 2019-08-23 17:11 評論0 收藏0
Javascript的數(shù)據(jù)結(jié)構(gòu)與算法(三)

摘要：存在好幾種方式來表示這種數(shù)據(jù)結(jié)構(gòu)。下面的示意圖展示了鄰接表數(shù)據(jù)結(jié)構(gòu)。在關(guān)聯(lián)矩陣中矩陣的行表示頂點(diǎn)列表示邊。廣度優(yōu)先搜索算法和深度優(yōu)先搜索算法基本上是相同的只有一點(diǎn)不同那就是待訪問頂點(diǎn)列表的數(shù)據(jù)結(jié)構(gòu)。 1 樹一個樹結(jié)構(gòu)包含一系列存在父子關(guān)系的節(jié)點(diǎn)。每個節(jié)點(diǎn)都有一個父節(jié)點(diǎn)(除了頂部的第一個節(jié)點(diǎn))以及零個或多個子節(jié)點(diǎn)。位于樹頂部的節(jié)點(diǎn)叫作根節(jié)點(diǎn)(11)。它沒有父節(jié)點(diǎn)。樹中的每個元素都叫作...

MasonEast 2019-08-21 11:24 評論0 收藏0
采用矩陣+深度優(yōu)先算法解決迷宮問題

摘要：所謂深度優(yōu)先算法，百科的解答是這樣的深度優(yōu)先搜索算法，簡稱是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。所謂深度優(yōu)先算法，百科的解答是這樣的深度優(yōu)先搜索算法（Depth-First-Search），簡稱DFS,是搜索算法的一種。是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深的搜索樹的分支。當(dāng)節(jié)點(diǎn)v的所有邊都己被探尋過...

yankeys 2019-08-20 13:54 評論0 收藏0