阿里云买啦域名怎么建设网站,贵安建设集团网站,蓝色网站设计,wordpress主题超限【NOIP提高组】引水入城 #x1f490;The Begin#x1f490;点点关注#xff0c;收藏不迷路#x1f490; 在一个遥远的国度#xff0c;一侧是风景秀美的湖泊#xff0c;另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊#xff0c;刚好构成一个N行M列的矩形#xff… 【NOIP提高组】引水入城 The Begin点点关注收藏不迷路 在一个遥远的国度一侧是风景秀美的湖泊另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊刚好构成一个N行M列的矩形如上图所示其中每个格子都代表一座城 市每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水现在要在某些城市建造水利设施。水利设施 有两种分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差将湖水从高处向低处输送。故一座城市能建造输水站的前提是 存在比它海拔更高且拥有公共边的相邻城市已经建有水利设施。 由于第N行的城市靠近沙漠是该国的干旱区所以要求其中的每座城市都建有水利 设施。那么这个要求能否满足呢如果能请计算最少建造几个蓄水厂如果不能求干 旱区中不可能建有水利设施的城市数目。
输入
输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M表示矩形的规模。 接下来N行每行M个正整数依次代表每座城市的海拔高度。输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M表示矩形的规模。 接下来N行每行M个正整数依次代表每座城市的海拔高度。
输出
输出有两行。如果能满足要求输出的第一行是整数1第二行是一个整数代表最少 建造几个蓄水厂如果不能满足要求输出的第一行是整数0第二行是一个整数代表有 几座干旱区中的城市不可能建有水利设施。
样例输入
2 5
9 1 5 4 3
8 7 6 1 2样例输出
1
1提示
【样例说明】只需要在海拔为9的那座城市中建造蓄水厂即可满足要求。 C语言实现
#include stdio.h
#include string.h// 定义二维数组的最大维度可根据实际需求调整
#define MAX_SIZE 520// 存储地形高度信息的二维数组
int h[MAX_SIZE][MAX_SIZE];
// 用于标记每个位置是否已被访问的二维数组
int vis[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最左列索引的二维数组
int l[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最右列索引的二维数组
int r[MAX_SIZE][MAX_SIZE];
// 定义四个方向的偏移量用于在二维数组中移动
int fx[4][2] { {0, -1}, {-1, 0}, {1, 0}, {0, 1} };
// 用于计数的变量根据不同情况有不同用途
int cnt;
// 存储二维数组的行数和列数
int n, m;
// 标记是否能从第一行到达最后一行所有位置的标志变量
int flag 1;// 深度优先搜索函数用于遍历二维数组
void dfs(int x, int y) {vis[x][y] 1; // 标记当前位置 (x, y) 已被访问int xx, yy;// 遍历四个方向for (int i 0; i 4; i) {xx x fx[i][0];yy y fx[i][1];// 判断新位置是否在合法范围内if (xx 1 || yy 1 || xx n || yy m) continue;// 如果当前位置的高度小于等于新位置的高度跳过if (h[x][y] h[xx][yy]) continue;// 如果新位置未被访问则递归调用dfs继续探索if (!vis[xx][yy]) dfs(xx, yy);// 更新当前位置能到达的最左列索引l[x][y] l[x][y] l[xx][yy]? l[x][y] : l[xx][yy];// 更新当前位置能到达的最右列索引r[x][y] r[x][y] r[xx][yy]? r[x][y] : r[xx][yy];}
}int main() {// 读取二维数组的行数和列数scanf(%d %d, n, m);// 初始化l数组为较大的值这里使用0x3f作为较大值的表示memset(l, 0x3f, sizeof(l));// 初始化最后一行的最左列索引和最右列索引为对应的列号for (int i 1; i m; i) {l[n][i] r[n][i] i;}// 读取二维数组中的地形高度信息for (int i 1; i n; i) {for (int j 1; j m; j) {scanf(%d, h[i][j]);}}// 从第一行的每个位置开始进行深度优先搜索for (int i 1; i m; i) {if (!vis[1][i]) dfs(1, i);}// 检查最后一行的每个位置是否都被访问到for (int i 1; i m; i) {if (!vis[n][i]) {flag 0;cnt;}}// 如果最后一行存在未被访问到的位置if (flag 0) {printf(0\n%d, cnt);return 0;}// 用于逐步扩展覆盖范围的变量表示当前覆盖范围的最左列int left 1;while (left m) {int maxr 0;// 遍历第一行的每个位置for (int i 1; i m; i) {if (l[1][i] left) {maxr maxr r[1][i]? maxr : r[1][i];}}cnt;left maxr 1;}printf(1\n%d, cnt);return 0;
}The End点点关注收藏不迷路
