有一个大小为n×m的长方形迷宫。用(r,c)表示从上往下第r行和从左往右第c列的单元。
每个格子最初都是空的。小鸿可以选择一些单元格(除了(x1,y1)和(x2,y2)),并在选择的单元格中放置一个障碍物。他想知道需要放置的最小障碍物数量,以便没有从(x1,y1)到(x2,y2)的路径(只能上下左右四个方向移动,不能斜着走)。
假设你是小鸿,请解决这个问题。
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6
4
2
3
在测试案例1中,你可以在(1,3), (2,3), (3,2), (4,2)上设置障碍。那么从(2,2)到(3,3)的路径将不存在。
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部cnt: 24251
关于网站改版