规范网站建设情况的报告,河南省住房和建设厅网站,免费公众号模板编辑器,30岁学前端开发是不是晚了文章目录 101.孤岛的总面积思路与重点 102.沉没孤岛思路与重点 103.水流问题思路与重点 104.建造最大岛屿思路与重点 101.孤岛的总面积
题目链接#xff1a;101.孤岛的总面积讲解链接#xff1a;代码随想录状态#xff1a;直接看题解了。
思路与重点
nextx或者nexty越界了… 文章目录 101.孤岛的总面积思路与重点 102.沉没孤岛思路与重点 103.水流问题思路与重点 104.建造最大岛屿思路与重点 101.孤岛的总面积
题目链接101.孤岛的总面积讲解链接代码随想录状态直接看题解了。
思路与重点
nextx或者nexty越界了则说明当前的x或y处于边界处所以当前的岛不是孤岛不能记入总面积。
#includeiostream
#includevector
using namespace std;
int dir[4][2] {0, 1, 0, -1, 1, 0 ,-1, 0};
void dfs(int tempans, bool flag, const vectorvectorint grid, vectorvectorbool visited, int x, int y){for(int i 0; i 4; i){int nextx x dir[i][0];int nexty y dir[i][1];if(nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()){flag false;continue;}if(!visited[nextx][nexty] grid[nextx][nexty] 1){visited[nextx][nexty] 1;tempans;dfs(tempans, flag, grid, visited, nextx, nexty);}}
}int main(){int ans 0;int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for(int i 0; i n; i){for(int j 0; j m; j){cin grid[i][j];}}vectorvectorbool visited(n, vectorbool(m, false));for(int i 0; i n; i){for(int j 0; j m; j){if(!visited[i][j] grid[i][j] 1){visited[i][j] true;bool flag true;int tempans 1;dfs(tempans, flag, grid, visited, i, j);if(flag) ans tempans;}}} cout ans endl;
}也可以将地图边缘的陆地全部变成海洋再遍历一遍陆地统计面积即可。
#include iostream
#include vector
using namespace std;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
int count; // 统计符合题目要求的陆地空格数量
void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 0;count;for (int i 0; i 4; i) { // 向四个方向遍历int nextx x dir[i][0];int nexty y dir[i][1];// 超过边界if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue;// 不符合条件不继续遍历if (grid[nextx][nexty] 0) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}// 从左侧边和右侧边 向中间遍历for (int i 0; i n; i) {if (grid[i][0] 1) dfs(grid, i, 0);if (grid[i][m - 1] 1) dfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j 0; j m; j) {if (grid[0][j] 1) dfs(grid, 0, j);if (grid[n - 1][j] 1) dfs(grid, n - 1, j);}count 0;for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 1) dfs(grid, i, j);}}cout count endl;
}102.沉没孤岛
题目链接102.沉没孤岛讲解链接代码随想录状态一遍AC。
思路与重点
先找到孤岛进行标记然后再DFS把孤岛全部沉没。
#includeiostream
#includevector
using namespace std;
int dir[4][2] {0, 1, 0, -1, 1, 0 ,-1, 0};
void dfs(bool flag, vectorvectorint grid, vectorvectorbool visited, int x, int y){for(int i 0; i 4; i){int nextx x dir[i][0];int nexty y dir[i][1];if(nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()){flag false;continue;}if(!visited[nextx][nexty] grid[nextx][nexty] 1){visited[nextx][nexty] 1;dfs(flag, grid, visited, nextx, nexty);}}
}void isoDfs(vectorvectorint grid, vectorvectorbool visited, int x, int y){for(int i 0; i 4; i){int nextx x dir[i][0];int nexty y dir[i][1];if(nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()){continue;}if(!visited[nextx][nexty] grid[nextx][nexty] 1){visited[nextx][nexty] 1;grid[nextx][nexty] 0;isoDfs(grid, visited, nextx, nexty);}}
}int main(){int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for(int i 0; i n; i){for(int j 0; j m; j){cin grid[i][j];}}vectorvectorbool visited(n, vectorbool(m, false));vectorpairint, int isoland;for(int i 0; i n; i){for(int j 0; j m; j){if(!visited[i][j] grid[i][j] 1){visited[i][j] true;bool flag true;dfs(flag, grid, visited, i, j);if(flag) isoland.push_back(make_pair(i,j));}}}for(int i 0; i n; i){for(int j 0; j m; j){visited[i][j] false;}}for(auto tempPair : isoland){grid[tempPair.first][tempPair.second] 0;isoDfs(grid, visited, tempPair.first, tempPair.second);}for(int i 0; i n; i){for(int j 0; j m; j){if(j 0) cout grid[i][j];else cout grid[i][j];}cout endl;}
}不用额外定义空间了标记周边的陆地可以直接改陆地为其他特殊值作为标记。步骤一深搜或者广搜将地图周边的 1 陆地全部改成 2 特殊标记步骤二将水域中间 1 陆地全部改成 水域0步骤三将之前标记的 2 改为 1 陆地
#include iostream
#include vector
using namespace std;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1}; // 保存四个方向
void dfs(vectorvectorint grid, int x, int y) {grid[x][y] 2;for (int i 0; i 4; i) { // 向四个方向遍历int nextx x dir[i][0];int nexty y dir[i][1];// 超过边界if (nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()) continue;// 不符合条件不继续遍历if (grid[nextx][nexty] 0 || grid[nextx][nexty] 2) continue;dfs (grid, nextx, nexty);}return;
}int main() {int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}// 步骤一// 从左侧边和右侧边 向中间遍历for (int i 0; i n; i) {if (grid[i][0] 1) dfs(grid, i, 0);if (grid[i][m - 1] 1) dfs(grid, i, m - 1);}// 从上边和下边 向中间遍历for (int j 0; j m; j) {if (grid[0][j] 1) dfs(grid, 0, j);if (grid[n - 1][j] 1) dfs(grid, n - 1, j);}// 步骤二、步骤三for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 1) grid[i][j] 0;if (grid[i][j] 2) grid[i][j] 1;}}for (int i 0; i n; i) {for (int j 0; j m; j) {cout grid[i][j] ;}cout endl;}
}103.水流问题
题目链接103.水流问题讲解链接代码随想录状态自己写了会儿再看题解。
思路与重点
我自己的代码过不了test5和test7也没找出问题在哪儿等二刷的时候再看看。感觉是**到达左边界和上边界的方法会包含先往右走再往上走**不能直接把dir分成两组来做。还是会超时直接看题解吧。
#includeiostream
#includevector
using namespace std;
int dir[2][2][2] {-1, 0, 0, -1, 1, 0, 0, 1};
bool dfs(const vectorvectorint grid, vectorvectorbool ans, int x, int y, int dirIdx){for(int i 0; i 2; i){int nextx x dir[dirIdx][i][0];int nexty y dir[dirIdx][i][1];if(nextx 0 || nextx grid.size() || nexty 0 || nexty grid[0].size()){return true;}if(grid[nextx][nexty] grid[x][y]){if(ans[nextx][nexty]) return true;if(dfs(grid, ans, nextx, nexty, dirIdx)) return true;}}return false;
}int main(){int n, m;cin n m;vectorvectorint grid(n, vectorint(m, 0));vectorvectorbool ans(n, vectorbool(m, false));for(int i 0; i n; i){for(int j 0; j m; j){cin grid[i][j];}}ans[n-1][0] true;ans[0][m-1] true;for(int i 0; i n; i){for(int j 0; j m; j){if(ans[i][j] false){bool flag1 dfs(grid, ans, i, j, 0);bool flag2 dfs(grid, ans, i, j, 1);if(flag1 flag2){ans[i][j] true;}}} }for(int i 0; i n; i){for(int j 0; j m; j){if(ans[i][j] true){cout i j endl;}} }return 0;
}我们可以反过来想从第一组边界上的节点逆流而上将遍历过的节点都标记上。同样从第二组边界的边上节点逆流而上将遍历过的节点也标记上。然后两方都标记过的节点就是既可以流太平洋也可以流大西洋的节点。
#include iostream
#include vector
using namespace std;
int n, m;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y) {if (visited[x][y]) return;visited[x][y] true;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue;if (grid[x][y] grid[nextx][nexty]) continue; // 注意这里是从低向高遍历dfs (grid, visited, nextx, nexty);}return;
}int main() {cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorbool firstBorder(n, vectorbool(m, false));// 标记从第一组边界上的节点出发可以遍历的节点vectorvectorbool secondBorder(n, vectorbool(m, false));// 从最上和最下行的节点出发向高处遍历for (int i 0; i n; i) {dfs (grid, firstBorder, i, 0); // 遍历最左列接触第一组边界dfs (grid, secondBorder, i, m - 1); // 遍历最右列接触第二组边界}// 从最左和最右列的节点出发向高处遍历for (int j 0; j m; j) {dfs (grid, firstBorder, 0, j); // 遍历最上行接触第一组边界dfs (grid, secondBorder, n - 1, j); // 遍历最下行接触第二组边界}for (int i 0; i n; i) {for (int j 0; j m; j) {// 如果这个节点从第一组边界和第二组边界出发都遍历过就是结果if (firstBorder[i][j] secondBorder[i][j]) cout i j endl;;}}}104.建造最大岛屿
题目链接104.建造最大岛屿讲解链接代码随想录状态暴力解法直接AC了。
思路与重点
依次将所有海洋变成陆地然后从变化的陆地出发找当前岛屿最大面积注意没有海洋的特殊情况。
#include iostream
#include vector
using namespace std;
int ans 1;
int n, m;
int dir[4][2] {-1, 0, 0, -1, 1, 0, 0, 1};
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int tempans) {if (visited[x][y]) return;visited[x][y] true;tempans;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue;if (grid[nextx][nexty] 0) continue; // 注意这里是从低向高遍历dfs (grid, visited, nextx, nexty, tempans);}return;
}int main() {cin n m;vectorvectorint grid(n, vectorint(m, 0));bool changeFlag false;for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}for (int i 0; i n; i) {for (int j 0; j m; j) {if(grid[i][j] 0){changeFlag true;vectorvectorbool visited(n, vectorbool(m, false));int tempans 0;grid[i][j] 1;dfs(grid, visited, i, j, tempans);ans ans tempans ? ans : tempans;grid[i][j] 0;}}} if(changeFlag) cout ans endl;else cout n * m endl;return 0;
}其实每次深搜遍历计算最大岛屿面积我们都做了很多重复的工作。只要用一次深搜把每个岛屿的面积记录下来就好。 第一步一次遍历地图得出各个岛屿的面积并做编号记录。可以使用map记录key为岛屿编号value为岛屿面积第二步再遍历地图遍历0的方格因为要将0变成1并统计该1由0变成的1周边岛屿面积将其相邻面积相加在一起遍历所有 0 之后就可以得出 选一个0变成1 之后的最大面积。
#include iostream
#include vector
#include unordered_set
#include unordered_map
using namespace std;
int n, m;
int count;int dir[4][2] {0, 1, 1, 0, -1, 0, 0, -1}; // 四个方向
void dfs(vectorvectorint grid, vectorvectorbool visited, int x, int y, int mark) {if (visited[x][y] || grid[x][y] 0) return; // 终止条件访问过的节点 或者 遇到海水visited[x][y] true; // 标记访问过grid[x][y] mark; // 给陆地标记新标签count;for (int i 0; i 4; i) {int nextx x dir[i][0];int nexty y dir[i][1];if (nextx 0 || nextx n || nexty 0 || nexty m) continue; // 越界了直接跳过dfs(grid, visited, nextx, nexty, mark);}
}int main() {cin n m;vectorvectorint grid(n, vectorint(m, 0));for (int i 0; i n; i) {for (int j 0; j m; j) {cin grid[i][j];}}vectorvectorbool visited(n, vectorbool(m, false)); // 标记访问过的点unordered_mapint ,int gridNum;int mark 2; // 记录每个岛屿的编号bool isAllGrid true; // 标记是否整个地图都是陆地for (int i 0; i n; i) {for (int j 0; j m; j) {if (grid[i][j] 0) isAllGrid false;if (!visited[i][j] grid[i][j] 1) {count 0;dfs(grid, visited, i, j, mark); // 将与其链接的陆地都标记上 truegridNum[mark] count; // 记录每一个岛屿的面积mark; // 记录下一个岛屿编号}}}if (isAllGrid) {cout n * m endl; // 如果都是陆地返回全面积return 0; // 结束程序}// 以下逻辑是根据添加陆地的位置计算周边岛屿面积之和int result 0; // 记录最后结果unordered_setint visitedGrid; // 标记访问过的岛屿for (int i 0; i n; i) {for (int j 0; j m; j) {count 1; // 记录连接之后的岛屿数量visitedGrid.clear(); // 每次使用时清空if (grid[i][j] 0) {for (int k 0; k 4; k) {int neari i dir[k][1]; // 计算相邻坐标int nearj j dir[k][0];if (neari 0 || neari n || nearj 0 || nearj m) continue;if (visitedGrid.count(grid[neari][nearj])) continue; // 添加过的岛屿不要重复添加// 把相邻四面的岛屿数量加起来count gridNum[grid[neari][nearj]];visitedGrid.insert(grid[neari][nearj]); // 标记该岛屿已经添加过}}result max(result, count);}}cout result endl;}
