有障碍的图的四联通问题的转化

问题是：一张网格图，存在一些障碍，每次上下左右走。问是否存在路径能从\((1,1)\to (N,M)\)。

对偶？名字是这个，就是图的四联通可以转化成不存在障碍八连通。注意障碍的联通是说第一行最后一列的障碍和第一列最后一行的障碍不连通。当要删障碍使存在四联通时，就是找最少删多少障碍使不存在障碍的八连通。

还有图的八连通问题可以转化成不存在障碍的四联通。