Readme

2556.Disconnect-Path-in-a-Binary-Matrix-by-at-Most-One-Flip

本题的基本思想是构造两条尽量不相交的合法路径（即能到达终点），他们一个靠近上轮廓，一个靠近下轮廓，如果两条路径在任何一点相交，那么该点必然就是“割点”，即critical point。这里，靠近上轮廓的路径指的是贪心地优先往右走，靠近下轮廓的路径指的是贪心地优先往下走。

但是注意，如果完全按照贪心的策略，路径有可能进入dead end而不会到达终点，他们不能算是“轮廓”。所以我们必须去除掉那些不可能到达终点的干扰点。怎么办呢？巧妙的方法是从右下角逆向（即向左和向上）走一遍。如果某一点的下方和右方都不是1，那么说明该点无法到达终点，即使该点grid值是1，我们也将其更改赋值为0. 这样我们得到一个新的grid，每个点都能到达终点。这样我们就可以得到上轮廓和下轮廓了。

注意到，上轮廓和下轮廓所走的步数必然是相等的，都是从起点开始通过m+n-2步走到终点。所以我们只需要用一个for循环，查看到达终点前的每一步时两条路径是否重合。

本题的另一个思想就是对于每个位置(i,j)，求起点到达该位置的方案数dp1[i][j]，另外求终点逆向到达该位置的方案数dp2[i][j]。如果dp1[i][j]*dp2[i][j] = dp1[m-1][n-1]，说明该点就是割点。但是对于本题的数据量，dp的值是2^1000，所以需要实时取模并会有冲突的风险。