问题是：一张网格图，存在一些障碍，每次上下左右走。问是否存在路径能从\((1,1)\to (N,M)\)。
对偶？名字是这个，就是图的四联通可以转化成不存在障碍八连通。注意障碍的联通是说第一行的障碍和第一列的障碍不连通。当要删障碍使存在四联通时，就是找最少删多少障碍使不存在障碍的八连通。
还有图的八连通问题可以转化成不存在障碍的四联通。
在网络流会有涉及。
例题：AT_arc214_f [ARC214F] Unpredictable Moves
问题是：一张网格图，存在一些障碍，每次上下左右走。问是否存在路径能从\((1,1)\to (N,M)\)。
对偶？名字是这个，就是图的四联通可以转化成不存在障碍八连通。注意障碍的联通是说第一行的障碍和第一列的障碍不连通。当要删障碍使存在四联通时，就是找最少删多少障碍使不存在障碍的八连通。
还有图的八连通问题可以转化成不存在障碍的四联通。
在网络流会有涉及。
例题：AT_arc214_f [ARC214F] Unpredictable Moves