LeetCode|200.岛屿数量--C++题解

Vaccae

发布于 2020-05-14 15:13:14

8430

发布于 2020-05-14 15:13:14

文章被收录于专栏：微卡智享

前言

这个是在边学习算法的时候正好也去LeetCode进行每日一题的研究，没想到自己做的算法第一题就是这个，正好也可以拿出来说，因为这个是前面《实战|OpenCV结合A*算法实现简单的运动路径规划》《实战|JPS跳点寻路实现运行路径规划》这两个算法中非常简单的版本，话不多说，直接开始吧。

题目

微卡智享

上面的题目中，我们可以看出来，只要是上下左右都有数字1相连的都算一个，这样让我们计算整个地图中有几个岛，因为示例1中可以看到连在一起的只有一个岛，我们拿示例2进行图像分析下：

解题思路

#	步骤
1	遍历整个表格地图（从左上角开始，左到右，上到下）
2	遇到数字为1的说明是岛开始进行连接区域计算
3	通过递归方式上下左右的判断是否为1，如果为1的话把1改为2即可
4	结束上面的递归后我们把铭岛数量加1

重点说明

上面的第3步中，当遇到数字为1的时候说明是岛了，那我们把这个标记为2（标记为2的作用是说明这个值已经检测过了，这样再遍历到下一个格时判断已经检测过的直接跳过就可以了，防止重复计算）

计算过程演示

从上面的计算过程的动图上，背景色变为橙色说明正在遍历的当前坐标，录第一格检测到是1（也就是岛）后，针对1开始向上下左右的方向去计算连接区域，通过递归的方式把可以连接的区域都修为2后，说明这个点已经计算完成，然后我们把岛的数量加1。

然后开始计算下一个点，当遇到为0的就继续往下遍历，遇到为2的说明该点已经在前面计算过了，无需要再进行计算，也直接跳到一下个，最终计算出结果为3个岛。

代码实现

//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。//岛屿总是被水包围，并且每座岛屿只能由水平方向和 / 或竖直方向上相邻的陆地连接形成。//此外，你可以假设该网格的四条边均被水包围。//示例 1://输入://11110//11010//11000//00000//输出 : 1
//示例 2 ://  输入 ://  11000//  11000//  00100//  00011//  输出 : 3
//  解释 : 每座岛屿只能由水平和 / 或竖直方向上相邻的陆地连接而成。
#include<iostream>#include<vector>
using namespace std;

vector<char> getvecchar(const char*);int CheckIsLand(vector<vector<char>>&);void CheckOut(int, int);vector<vector<char>> maze;


int main(int argc, char** argv) {
  vector<vector<char>> site;  site.push_back(getvecchar("11110"));  site.push_back(getvecchar("11010"));  site.push_back(getvecchar("11000"));  site.push_back(getvecchar("00000"));
  vector<vector<char>> site2;  site2.push_back(getvecchar("11000"));  site2.push_back(getvecchar("11000"));  site2.push_back(getvecchar("00100"));  site2.push_back(getvecchar("00011"));
  vector<vector<char>> site3;  site3.push_back(getvecchar("01010"));  site3.push_back(getvecchar("11010"));  site3.push_back(getvecchar("00100"));  site3.push_back(getvecchar("11111"));
  int num = CheckIsLand(site);
  cout << "num:" << num << endl;
  num = CheckIsLand(site2);
  cout << "num:" << num << endl;
  num = CheckIsLand(site3);
  cout << "num:" << num << endl;
  return 0;}
vector<char> getvecchar(const char* chr) {  vector<char> vdata;  vdata.insert(vdata.end(), chr, chr + (strlen(chr)));  return vdata;}


//检测岛int CheckIsLand(vector<vector<char>>& site) {  maze = vector<vector<char>>(site);
  int num = 0;  for (int row = 0; row < maze.size(); ++row) {    for (int col = 0; col < maze[0].size(); ++col) {      if (maze[row][col] == '1') {        CheckOut(row, col);        num++;      }    }  }  return num;}
void CheckOut(int row, int col) {  //超出边界返回0  if (row<0 || col<0 || row>maze.size() - 1 || col>maze[0].size() - 1)return;
  //判断当前坐标是陆地则开始计算陆地连接  if (maze[row][col] == '1') {    //先修改为已计算    maze[row][col] = '2';
    //计算4个方向的值     //左边点    CheckOut(row, col - 1);    //右边点    CheckOut(row, col + 1);    //上边点    CheckOut(row - 1, col);    //下边点    CheckOut(row + 1, col);  }}