编程题
### 问题描述 公园里正在移栽一批树木,但是园林施工工人不慎挖断了坐标为 $(x_0,y_0)$ 处的地下灌溉水管,不远处地上还固定有 $k$ 个照明用的地灯。 为了保护所有地灯不被泡水产生危险,在水喷出之前你有**足够的时间**在地图中的任意位置放置若干障碍物来保护这些地灯不被泡水,水喷出之后会以极短的时间淹没周边相邻的区域,但是水位最终不会高于障碍物的高度。依据输入地图及规则,输出保护所有路灯不被泡水最少所需放置的障碍物数量。 ### 输入格式 第一行输入三个正整数 $m$,$n$,$k$ 代表地图的长和宽以及地灯的数量 $k$ 。 第二行输入两个正整数 $x_0$,$y_0$ 代表漏水位置的坐标。 接下来 $k$ 行,每行两个整数 $x_i$,$y_i$ 代表第 $i$ 个地灯的坐标。 ### 输出格式 在一行中输出一个整数,代表最少放置多少障碍物才能保护所有地灯不被水淹,如果不能保护所有灯则输出 $-1$ 。 ### 输入样例 ``` 3 5 1 1 0 1 4 ``` ### 输出样例 ``` 3 ``` ### 样例解释 用 $A$ 表示地灯,用 $B$ 表示出水口,用 $*$ 表示障碍物,用 $.$ 表示空地,那么放置方块最少的一种可行的方案如下。 ``` ..*.. A.*.B ..*.. ``` ### 数据规模 $2\leq m,n\leq 10^5$,$0