填空题
接下来N行，每行M个正整数，依次代表每座城市的海拔高度，且每座城市的海拔高度不高于1e6。输入样例： 2 5 9 1 5 4 3 8 7 6 1 2 输出描述： 输出有两行。
如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；
如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座毗邻沙漠的城市不可能建有水利设施。输出样例 1 1
引水入城
发布于 2022-03-03 17:37:00
如上图所示，在N行M列的矩形表示的区域范围内，其中每个格子都代表一座城市，每座城市都有一个海拔高度。现在要在某些城市建造蓄水厂和输水站以满足区域内居民饮水需求。
蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的蓄水池中。只有与湖泊毗邻的第1行的城市可以建造蓄水厂。
输水站的功能则是通过输水管线利用高度落差，将湖水从高处向低处输送。一座城市能建造输水站的前提，是存在比它海拔更高且拥有公共边的相邻城市，已经建有水利设施。
值得注意的是，该区域内第N行的城市毗邻沙漠，供水严重缺乏，故方案中的每座城市都必须建有水利设施。
请问能否设计出满足以上需求的方案？
如果能，请计算最少建造几个蓄水厂；
如果不能，求干旱区中不可能建有水利设施的城市数目。
输入描述：
输入的第一行是两个正整数N和M，表示矩形的规模。接下来N行，每行M个正整数，依次代表每座城市的海拔高度，且每座城市的海拔高度不高于1e6。输入样例： 2 5 9 1 5 4 3 8 7 6 1 2 输出描述： 输出有两行。
如果能满足要求，输出的第一行是整数1，第二行是一个整数，代表最少建造几个蓄水厂；
如果不能满足要求，输出的第一行是整数0，第二行是一个整数，代表有几座毗邻沙漠的城市不可能建有水利设施。输出样例 1 1
关注者
0
被浏览
10
