判斷點的連通性最優演算法？

02-18

給定一個M*N的矩陣D,D中的元素只取0，1。從矩陣的左下角出發，只能按下圖的方向行走，其中矩陣元素的0表示不能走，1表示能走，判斷能否到達矩陣的右上角。
我想到了一個遞歸演算法可以解決該問題，但是演算法複雜度為 $O(N^2)$ 。

private int isConect(int[] mat, int x, int y) { int len1 = mat.GetLength(0); int len2 = mat.GetLength(1); if (x &>= len1 || y &>= len2 || mat[x, y] != 1) return 0; mat[x, y] = 0; if (x == len1 - 1 y == len2 - 1) return 1;
return isConect(mat, x + 1, y) + isConect(mat, x, y + 1) + isConect(mat, x + 1, y + 1); }
再判斷結果是否大於0即可
感覺有演算法複雜度為 $O(N)$ 的解法，是否存在呢？求指教。

我認為沒有更佳的。最壞情況需遍歷所有元素。

---

一個改進方式是最後遞歸時用||代替+，返回bool。短路評估就可以。

另一種改進方式是把矩陣以二進位表示，如用64位整數。然後用逐行掃描的方式，並用位 AND 及 shift 來計算下一行的可行位。這樣只需遞代並且係數低，空間也是O(n)。

這個問題，若是考察最壞情況的運行時間，自然是 $O(N^2)$ 了。

但是這是最壞情況。平均情況下效率更高的演算法，是可以有的。

我們假定在這個 $N*M$ 的矩陣中，共有 $K$ 個障礙位，下面給出一個時間複雜度為 $O(K)$ 的演算法。

首先，對K個障礙位進行以x坐標為第一關鍵字，y坐標為第二關鍵字的雙關鍵字排序。因為坐標值域範圍很小，使用線性的桶排序即可。
第 $i$ 行的 $T_i$ 個障礙把該行分成了 $T_i + 1$ 個可行區間。
從第 $N+1$ 行向上進行掃描。初始化當前可行區間序列為 $[0, M)$ 。
每掃描到第 $i$ 行，取當前可行區間序列和該行 $T_i+1$ 個可行區間的交集，用其替換當前可行區間序列。替換完成後，當前可行區間序列中所有區間的右端點 $+1$ 。
掃描到第一行，檢查第一行右端點是否包含在當前可行區間序列內，返回結果。

並查集

謝謝邀請，抱歉很少上知乎了所以一直沒有來回答。

按複雜度來說，題主提出的演算法應該已經是最優了（順便說一句，題主的演算法複雜度其實是 $O(n)$ 不是 $O(n^2)$ ）。不過比遞歸稍微快一點、代碼再稍微簡潔一點的話還是可以的，用遞推式動態規劃就好：

for (int i = 0; i &< len1; i++) for (int j = 0; j &< len2; j++) mat[i][j] = (mat[i][j] == 1 (i-1 &>= 0 mat[i-1][j] == 1 || j-1 &>= 0 mat[i][j-1] == 1));

return (mat[len1-1][len2-1] == 1);

希望有幫助~

並查集適合你查多次

這個圖的走法不是有向的嗎，並查集可以嗎。。。

複雜度上講已經是極限了 Milo Yip說的對這是個必須在狀態空間大小的時間裡解決的問題

可以改進的地方在於題主可以正經地寫個dfs這樣找到解就可以退了題主意淫的這個會多跑出幾個解再退

看看數據結構，圖那一部分

說個蠢得。

做出關聯矩陣，用Warshell演算法計算傳遞閉包，

直到發現矩陣對應點上的值變成1。

-----------

題主這個演算法我實現過。。

至多變為剪枝樹。

並不會快太多。