黄石网站建设哪家好,厦门seo关键词优化代运营,怎么做网站相册,中企动力是什么性质的公司101. 孤岛的总面积
卡码网#xff1a;101. 孤岛的总面积(opens new window)
题目描述
给定一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的矩阵#xff0c;岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域#xff0c;且完全被水域单…101. 孤岛的总面积
卡码网101. 孤岛的总面积(opens new window)
题目描述
给定一个由 1陆地和 0水组成的矩阵岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要计算所有孤岛的总面积岛屿面积的计算方式为组成岛屿的陆地的总数。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。之后 N 行每行包含 M 个数字数字为 1 或者 0。
输出描述
输出一个整数表示所有孤岛的总面积如果不存在孤岛则输出 0。
我的算法dfs
在dfs的基础上分别计算每次孤岛的面积计入thissize计算完后加到total上
每次遇到一个陆地且未访问过进行dfs访问 核心一旦遇到一个陆地接触到了边界——那么thissize将始终归为0 即使thissize归为0也需要计算把相接处的陆地visit掉 所以采用了在dfs函数开头分类讨论 遇到边界了——size为0 本情况非孤岛size已经为0了——永远为0 初始情况size记为-1且初始情况 不涉及到边界——size1 否则初始情况标记为0会和非孤岛 size已经为0混淆 其他情况下size
注意初始情况是怎么被启动的
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.hint move[4][2]{1,0,0,1,-1,0,0,-1};
int this_size;void dfs(int i,int j,int **box,int**visit,int m,int n){if(i0 || in-1 || j0 || jm-1 || this_size0){this_size0;}else if(this_size-1) this_size1;else this_size;for(int k0;k4;k){int move_i imove[k][0];int move_j jmove[k][1];if(move_i 0 move_in move_j0 move_jm box[move_i][move_j]1 visit[move_i][move_j]0){visit[move_i][move_j]1;//printf(in:%d %d size%d\n,move_i,move_j,this_size);dfs(move_i,move_j,box,visit,m,n);}}
}int main(){int n,m;scanf(%d%d,n,m);int** box(int**)malloc(sizeof(int*)*n);int **visit(int**)malloc(sizeof(int*)*n);for (int i0;in;i){box[i](int*)malloc(sizeof(int)*m);visit[i](int*)malloc(sizeof(int)*m);for(int j0;jm;j){scanf(%d,box[i][j]);visit[i][j]0;}}int total_area0;for (int i0;in;i){for(int j0;jm;j){if(box[i][j]1 visit[i][j]0){this_size-1;visit[i][j]1;dfs(i,j,box,visit,m,n);total_areatotal_areathis_size;}}}printf(%d,total_area);return 0;
}
改成bfs
int front-1;
int rear-1;
int queue[10000][2];bool judge(int i,int j,int n,int m){if(i 0 || in-1 || j0 || jm-1) return true;else return false;
}void bfs(int i,int j,int**box,int**visit,int m,int n){rear;queue[rear][0]i;queue[rear][1]j;visit[i][j]1;if(judge(i,j,n,m)) this_size0;else this_size1;while(front!rear){front;int xiqueue[front][0];int xjqueue[front][1];for(int k0;k4;k){int fiximove[k][0];int fjxjmove[k][1];if(fi0 fin fj0 fjm box[fi][fj]1 visit[fi][fj]0){if(judge(fi,fj,n,m) || this_size0) this_size0;else this_size;rear;queue[rear][0]fi;queue[rear][1]fj;visit[fi][fj]1;}}}
}或者
也可以考虑
本题要求找到不靠边的陆地面积那么我们只要从周边找到陆地然后 通过 dfs或者bfs 将周边靠陆地且相邻的陆地都变成海洋然后再去重新遍历地图 统计此时还剩下的陆地就可以了。
如图在遍历地图周围四个边靠地图四边的陆地都为绿色 在遇到地图周边陆地的时候将1都变为0此时地图为这样 102. 沉没孤岛
卡码网题目链接ACM模式(opens new window)
题目描述
给定一个由 1陆地和 0水组成的矩阵岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。
现在你需要将所有孤岛“沉没”即将孤岛中的所有陆地单元格1转变为水域单元格0。
输入描述
第一行包含两个整数 N, M表示矩阵的行数和列数。
之后 N 行每行包含 M 个数字数字为 1 或者 0表示岛屿的单元格。
输出描述
输出将孤岛“沉没”之后的岛屿矩阵。 分析
思路依然是从地图周边出发将周边空格相邻的陆地都做上标记然后在遍历一遍地图遇到 陆地 且没做过标记的那么都是地图中间的 陆地 全部改成水域就行。
有的录友可能想我在定义一个 visited 二维数组单独标记周边的陆地然后遍历地图的时候同时对 数组board 和 数组visited 进行判断决定 陆地是否变成水域。
这样做其实就有点麻烦了不用额外定义空间了标记周边的陆地可以直接改陆地为其他特殊值作为标记。
步骤一深搜或者广搜将地图周边的 1 陆地全部改成 2 特殊标记
步骤二将水域中间 1 陆地全部改成 水域0
步骤三将之前标记的 2 改为 1 陆地
如图 #include stdio.h
#include stdlib.h
#include stdbool.h
#include string.hint move[4][2]{1,0,0,1,-1,0,0,-1};void dfs(int i,int j,int**box,int **visit,int m,int n){visit[i][j]1;box[i][j]2;for(int k0;k4;k){int moveiimove[k][0];int movejjmove[k][1];if(movei0 movej0 movein movejm visit[movei][movej]0 box[movei][movej]1){dfs(movei,movej,box,visit,m,n);}}
}int main(){int n,m;scanf(%d%d,n,m);int** box(int**)malloc(sizeof(int*)*n);int **visit(int**)malloc(sizeof(int*)*n);for (int i0;in;i){box[i](int*)malloc(sizeof(int)*m);visit[i](int*)malloc(sizeof(int)*m);for(int j0;jm;j){scanf(%d,box[i][j]);visit[i][j]0;}}for (int i0;in;i){if(box[i][0]1 visit[i][0]0){dfs(i,0,box,visit,m,n);}if(box[i][m-1]1 visit[i][m-1]0){dfs(i,m-1,box,visit,m,n);}}for (int i0;in;i){if(box[0][i]1 visit[0][i]0){dfs(0,i,box,visit,m,n);}if(box[n-1][i]1 visit[n-1][i]0){dfs(n-1,i,box,visit,m,n);}}for (int i0;in;i){for(int j0;jm;j){if(box[i][j]1) box[i][j]0;else if(box[i][j]2) box[i][j]1;printf(%d ,box[i][j]);}printf(\n);}return 0;
}
或者bfs
int front-1,rear-1;
int queue[1000][2];void bfs(int i,int j,int**box,int **visit,int m,int n){rear;queue[rear][0]i;queue[rear][1]j;visit[i][j]1;box[i][j]2;while(rear!front){front;int xiqueue[front][0];int xjqueue[front][1];for(int k0;k4;k){int moveiximove[k][0];int movejxjmove[k][1];if(movei0 movej0 movein movejm visit[movei][movej]0 box[movei][movej]1){rear;queue[rear][0]movei;queue[rear][1]movej;visit[movei][movej]1;box[movei][movej]2;}}}} 103. 水流问题
卡码网题目链接ACM模式(opens new window)
题目描述
现有一个 N × M 的矩阵每个单元格包含一个数值这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界而矩阵的右边界和下边界被视为第二组边界。
矩阵模拟了一个地形当雨水落在上面时水会根据地形的倾斜向低处流动但只能从较高或等高的地点流向较低或等高并且相邻上下左右方向的地点。我们的目标是确定那些单元格从这些单元格出发的水可以达到第一组边界和第二组边界。
输入描述
第一行包含两个整数 N 和 M分别表示矩阵的行数和列数。
后续 N 行每行包含 M 个整数表示矩阵中的每个单元格的高度。
输出描述
输出共有多行每行输出两个整数用一个空格隔开表示可达第一组边界和第二组边界的单元格的坐标输出顺序任意。
分析
一、从高往低寻找
小的数 无法继承大的数的遍历结果导致每个数字都必须从头遍历复杂度太高
遍历每一个节点是 m * n遍历每一个节点的时候都要做深搜深搜的时间复杂度是 m * n
那么整体时间复杂度 就是 O(m^2 * n^2) 这是一个四次方的时间复杂度。 二、从低往高
从第一组边界上的节点 逆流而上将遍历过的节点都标记上。
同样从第二组边界的边上节点 逆流而上将遍历过的节点也标记上。
然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
从第一组边界边上节点出发如图 从第二组边界上节点出发如图 关于dfs函数搜索的过程 时间复杂度是 O(n * m)这个大家比较容易想。
关键看主函数那么每次dfs的时候上面还是有for循环的。
第一个for循环时间复杂度是n * (n * m) 。
第二个for循环时间复杂度是m * (n * m)。
所以本题看起来 时间复杂度好像是 n * (n * m) m * (n * m) (m * n) * (m n) 。
其实这是一个误区大家再自己看 dfs函数的实现其实 有visited函数记录 走过的节点而走过的节点是不会再走第二次的。
所以 调用dfs函数只要参数传入的是 数组 firstBorder那么地图中 每一个节点其实就遍历一次无论你调用多少次。
同理调用dfs函数只要 参数传入的是 数组 secondBorder地图中每个节点也只会遍历一次。
所以以下这段代码的时间复杂度是 2 * n * m。 地图用每个节点就遍历了两次参数传入 firstBorder 的时候遍历一次参数传入 secondBorder 的时候遍历一次。
#include stdio.h
#include stdlib.h
#include stdbool.h
#include string.hint move[4][2]{1,0,0,1,-1,0,0,-1};int main(){int n,m;scanf(%d%d,n,m);int** box(int**)malloc(sizeof(int*)*n);int **visit1(int**)malloc(sizeof(int*)*n);int **visit2(int**)malloc(sizeof(int*)*n);for (int i0;in;i){box[i](int*)malloc(sizeof(int)*m);visit1[i](int*)malloc(sizeof(int)*m);visit2[i](int*)malloc(sizeof(int)*m);for(int j0;jm;j){scanf(%d,box[i][j]);visit1[i][j]0;visit2[i][j]0;}}for (int i0;in;i){if(visit1[i][0]0) dfs(i,0,box,visit1,m,n);if(visit2[i][m-1]0) dfs(i,m-1,box,visit2,m,n); }for (int i0;im;i){if(visit1[0][i]0) dfs(0,i,box,visit1,m,n);if( visit2[n-1][i]0) dfs(n-1,i,box,visit2,m,n);}for (int i0;in;i){for(int j0;jm;j){if(visit1[i][j]1 visit2[i][j]1) printf(%d %d\n,i,j); }}return 0;
}
bfs:
int front-1,rear-1;
int queue[1000][2];void bfs(int i,int j,int**box,int **visit,int m,int n){rear;queue[rear][0]i;queue[rear][1]j;visit[i][j]1;while(rear!front){front;int xiqueue[front][0];int xjqueue[front][1];for(int k0;k4;k){int moveiximove[k][0];int movejxjmove[k][1];if(movei0 movej0 movein movejm visit[movei][movej]0 box[movei][movej]box[xi][xj]){rear;queue[rear][0]movei;queue[rear][1]movej;visit[movei][movej]1;}}}}
