一個與矩陣有關的演算法問題？

01-11

有n*m的方格，其中有最多40個格子不能走，從左上角走到右下角得最短路徑中有多少種走法。
n&<1000000000 m&<50

確實是動態規劃，但是不是把矩陣遍歷一遍，首先因為是最短路徑，路徑的方向一定只能向右和向下，這樣我們就可以用組合數直接算出兩點間移動的方案數，然後關注那些不合法的格子，另

f[i][j]表示從起點到達i行j列這個不合法格子且不經過其它任意不合法格子的方案數，這樣的話可以得到轉移 f[i][j] = C(i + j, i) - sigma(f[k][l] * C（i-k，j-l）) /* [k][l]表示所有能到達[i][j]的不合法格子 */ 假如把[n][m]也看做一個不合法的點，就可以發現f[n][m]就是所求的答案（不太清楚會不會有些細節問題...感覺沒什麼問題）複雜度是不合法格子數的平方 + 組合數計算組合數計算的時間可能有點緊（但是m很小假如你有取模的話就沒問題的樣子）... // 之前的轉移存在問題.. 以更正

Problem - 722E - Codeforces 改改範圍就是這個題了, 題解在這裡 Intel Code Challenge Elimination Round (div.1 + div.2 combined) editorial - Codeforces

這題有多種不同複雜度的做法。記 $k$ 為不能走的格子數（$kle 40$），$a_{i,j}$ 表示：若第 $i$ 行第 $j$ 列的格子不能走，則 $a_{i,j}=0$（假定網格外的格子都不能走），否則 $a_{i,j}=1$。

1、$O(nm)$

設計狀態 $f(i,j)$ 表示從左上角走到第 $i$ 行第 $j$ 列的路徑條數。由於最短路徑只能往下或者往右，枚舉最後一步走的方向，可得

$$f(i,j)=egin{cases}0,a_{i,j}=0,\1,i=j=1,\f(i,j-1)+f(i-1,j),mathrm{otherwise}end{cases}$$

答案為 $f(n,m)$，複雜度為 $O(nm)$。

這個做法的優點是複雜度不依賴於 $k$，缺點是沒有利用到問題中 $m,k$ 很小的性質，所以並不能通過。

2、$O(m^3k)$

考慮離散化所有不能走的格子所在的行，離散化中加入第 $1$ 行和第 $n$ 行，記為 $r_1=1 &< r_2 &< cdots &< r_{k"}=n$（$k" le k+2$），然後設 $f(i,j)$ 為從左上角走到第 $r_i$ 行第 $j$ 列的路徑條數，轉移時枚舉第一次離開第 $r_{i-1}$ 行時的格子，在 $r_{i-1}$ 和 $r_i$ 這兩行之間所有格子都可以走，因此從 $(a,b)$ 走到 $(a+x,b+y)$ 的最短路徑條數為從 $x+y$ 步移動中選出 $y$ 步往右的方案數，即 $C_{x+y}^y$，可以得到

$$f(i,j)=egin{cases}0,a_{i,j}=0,\1,i=j=1,\a_{i,j-1}f(i,j-1),i=1,j&>1,\f(i,j-1)+sum_{j"=1}^jf(i-1,j")C_{r_i-r-{i-1}-1+j-j"}^{j-j"},mathrm{otherwise}end{cases}$$

答案為 $f(k",m)$，複雜度為 $O(m^3k)$。注意需要 $O(m)$ 的時間計算一個組合數。

這個做法的優點是當 $m$ 很小時，可以把障礙個數擴大到輸入規模。

3、$O(mk^2)$

記所有不能走的格子坐標分別為 $(x_1,y_1),(x_2,y_2),cdots,(x_k,y_k)$，再記 $x_0=n,y_0=m$，即 $(x_0,y_0)$ 為右下角。

設 $f(i)$ 為從 $(1,1)$ 走到 $(x_i,y_i)$，且中間不經過任何其它 $(x_j,y_j)$ 的路徑條數。如果允許經過所有格子，那麼路徑條數顯然是 $C_{x_i+y_i-2}^{y_i-1}$，現在要從中扣除經過其它 $(x_j,y_j)$ 的路徑數。枚舉路上第一次經過的 $(x_j,y_j)$，可以得到

$$f(i)=C_{x_i+y_i-2}^{y_i-1}-sum_{1le jle k,j
e i,x_jle x_i,y_jle y_i}f(j)C_{x_i-x_j+y_i-y_j}^{y_i-y_j}$$

答案為 $f(0)$，複雜度為 $O(k^2)$。注意需要 $O(m)$ 的時間計算一個組合數。

這種演算法對於本題來說最優的，除計算組合數以外複雜度不依賴於 $m$。

更多問題：能否優化計算組合數的複雜度？

某一列全是空的話，其實轉移都是一樣的，搞個矩陣乘一下，其他的就相當於多個bfs吧。

因為是要最短路徑需要處理一下，就是到這一列了，每一行的最短步數（算個相對的就行，最短的用0）

大概複雜度就是50*40的bfs，或者把兩邊空的列也算上50*120的bfs。矩陣是50^3*log

可以按照有障礙的位置的坐標先離散化，然後得到一個帶權重規模更小的網格，然後把網格的邊緣，和四角當成點，同一格的四邊互相連通，在這個圖上dp，轉移時區分對待，邊到邊，和邊到角的轉移。捨棄非最優轉移。應該可以吧。

好吧我意識到我答案有問題了。。

我能想到的做法就是在障礙格附近的列做bfs，其他的列用組合數來算。不過這樣已經不怎麼好寫了。

取決於不能走的格子的分布……

做法就是動態規劃。

小學奧賽加強版，從左上角的點標1，左邊界和上邊界的點都標1，每個點的值取決於其上方和左方相鄰點之和，如果某一個相鄰點不能通過，其值取0。一直算到右下角即可，O（mn）。應該直接TLE的樣子。

額，初始的時候應該考慮邊界點被障礙點擋住從而需要取為0的問題

矩陣優化dp搞定啦。。。反正就先這樣吧