矩陣路徑深度搜索

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

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

情景

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

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/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)是隊(duì)列。深度優(yōu)先搜索算法數(shù)據(jù)結(jié)構(gòu)是棧。定義圖和散列表、二叉樹(shù)一樣，是一種非線(xiàn)性數(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 評(píng)論0 收藏0
[Algo] Longest Descending Path 滑雪問(wèn)題

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

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

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

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

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

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

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

yankeys 2019-08-20 13:54 評(píng)論0 收藏0