走格子路線算法？給定一個(gè)二維數(shù)組，找出是否有從左上角到右下角的路徑。在給定的二維數(shù)組中，當(dāng)單元格值為-1時(shí)，表示不能通過(guò)；當(dāng)單元格值為0時(shí)，表示可以通過(guò)。例如：給定如下二維數(shù)組：{0，0，0，-1，0

走格子路線算法？

給定一個(gè)二維數(shù)組，找出是否有從左上角到右下角的路徑。在給定的二維數(shù)組中，當(dāng)單元格值為-1時(shí)，表示不能通過(guò)；當(dāng)單元格值為0時(shí)，表示可以通過(guò)。

例如：給定如下二維數(shù)組：

{0，0，0，-1，0}，

{1，0，0，-1，-1}，]{0，0，-1，0}，

{1，0，0，0，0}，

{0，0，-1，0}]路徑存在，返回yes

{0，0，0，-1，0}，

{1，0，0，-1}，

{0，0，-1，0}，

{1，0，-1，0}，

{，0}

路徑不存在，返回no

算法分析

解決此問(wèn)題的簡(jiǎn)單方法是使用BFS或DFS算法來(lái)查找是否有一條合格的路徑（path）。

更好的解決方案是通過(guò)將所有可訪問(wèn)節(jié)點(diǎn)的值更改為1來(lái)標(biāo)記它們。

首先，將左上角第一個(gè)元素的值標(biāo)記為1。然后獲取第一行中的下一個(gè)（當(dāng)前）值，并將其與上一個(gè)值進(jìn)行比較。僅當(dāng)當(dāng)前值可到達(dá)（不等于-1）時(shí)，才將其設(shè)置為上一個(gè)值。類似地，對(duì)列值執(zhí)行相同的操作，方法是將當(dāng)前值與前一列的值（如果可以訪問(wèn)）進(jìn)行比較并進(jìn)行設(shè)置。

然后從第一行和第一列開始，獲取前一行和前一列的值。找到它們之間的最大值，并將當(dāng)前索引設(shè)置為該最大值。如果當(dāng)前索引值為-1，則沒(méi)有更改。

最后，如果右下角的最終索引為1，則返回“是”，否則返回“否”。