一个与矩阵有关的算法问题
Problem - 722E - Codeforces 改改范围就是这个题了, 题解在这里 Intel Code Challenge Elimination Round (div.1 + div.2 combined) editorial - Codeforces
■网友
这题有多种不同复杂度的做法。记 $k$ 为不能走的格子数（$k\\le 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)=\\begin{cases}0,\u0026amp;a_{i,j}=0,\\\\1,\u0026amp;i=j=1,\\\\f(i,j-1)+f(i-1,j),\u0026amp;\\mathrm{otherwise}\\end{cases}$$
答案为 $f(n,m)$，复杂度为 $O(nm)$。
这个做法的优点是复杂度不依赖于 $k$，缺点是没有利用到问题中 $m,k$ 很小的性质，所以并不能通过。
2、$O(m^3k)$
考虑离散化所有不能走的格子所在的行，离散化中加入第 $1$ 行和第 $n$ 行，记为 $r_1=1 \u0026lt; r_2 \u0026lt; \\cdots \u0026lt; r_{k\u0026#39;}=n$（$k\u0026#39; \\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)=\\begin{cases}0,\u0026amp;a_{i,j}=0,\\\\1,\u0026amp;i=j=1,\\\\a_{i,j-1}f(i,j-1),\u0026amp;i=1,j\u0026gt;1,\\\\f(i,j-1)+\\sum_{j\u0026#39;=1}^jf(i-1,j\u0026#39;)C_{r_i-r-{i-1}-1+j-j\u0026#39;}^{j-j\u0026#39;},\u0026amp;\\mathrm{otherwise}\\end{cases}$$
答案为 $f(k\u0026#39;,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_{1\\le j\\le k,j\e i,x_j\\le x_i,y_j\\le 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$。
更多问题：能否优化计算组合数的复杂度？
■网友
小学奥赛加强版，从左上角的点标1，左边界和上边界的点都标1，每个点的值取决于其上方和左方相邻点之和，如果某一个相邻点不能通过，其值取0。一直算到右下角即可，O（mn）。应该直接TLE的样子。额，初始的时候应该考虑边界点被障碍点挡住从而需要取为0的问题
■网友
某一列全是空的话，其实转移都是一样的，搞个矩阵乘一下，其他的就相当于多个bfs吧。因为是要最短路径需要处理一下，就是到这一列了，每一行的最短步数（算个相对的就行，最短的用0）大概复杂度就是50*40的bfs，或者把两边空的列也算上50*120的bfs。矩阵是50^3*log
■网友
可以按照有障碍的位置的坐标先离散化，然后得到一个带权重规模更小的网格，然后把网格的边缘，和四角 当成点，同一格的四边互相连通，在这个图上dp，转移时区分对待，边到边，和边到角的转移。舍弃非最优转移。应该可以吧。好吧我意识到我答案有问题了。。
推荐阅读
- 同比■同比增长7.1%！2021年的第一个节你花了多少钱？
- “他是我第一个会说普通话的老师”：一对师生折射青海山村蝶变
- 过节■江苏省委省政府办公厅下发关于做好2021年元旦春节期间有关工作的通知
- 有必要重新开个C店吗
- 大学再有三个月就结束了，没学到知识，参加一个软件测试培训机构好吗
- 汽车|长安UNI-K又将开创一个新的"引力"纪元？
- 神话|武汉传奇父亲：一个平行班孩子创造的高考神话（感动上万家长）
- 王者荣耀李白能不能出肉
- 直播会成为品牌传播的另一个途径么有哪些可行的方法感觉有戏又没头绪好捉急。
- 怎样成为一名合格的Python程序员?