2026年2月26日
有障碍的图的四联通问题的转化
摘要： 问题是：一张网格图，存在一些障碍，每次上下左右走。问是否存在路径能从\((1,1)\to (N,M)\)。 对偶？名字是这个，就是图的四联通可以转化成不存在障碍八连通。注意障碍的联通是说第一行最后一列的障碍和第一列最后一行的障碍不连通。当要删障碍使存在四联通时，就是找最少删多少障碍使不存在障碍的八连 阅读全文
posted @ 2026-02-26 10:24 lghjl 阅读(4) 评论(0) 推荐(0)