一：图像渲染

题目：

有一幅以m*n的二维数组表示的图画image，其中image[i][j]表示该图像的像素值大小

给出三个整数sr,sc,和color，从像素image[i][j]开始对图像进行上色填充，为了完成上色工作，从初始像素开始，记录初始坐标的上下左右四个方向上相邻且同色的像素点，接着再记录与这些像素点相邻且同色的新像素点......重复此过程，将所有有记录的像素点的颜色改为color，最后返回经过上色渲染后的图像。

方法：

1：画出决策树（同之前的题目基本一致，故省略）

2：算法原理

基本思路：分为两种情况，如果image[sr][sc]等于color，可以直接返回image，如果不相等，从当前位置开始，利用dx[4]，和dy[4]两个数组，对其上下左右四个位置是否需要渲染进行判断，符合条件对其进行递归

dfs函数：

void dfs(iamge, i, j, color)（数组，当前位置，需要渲染改变的值）

不需要设置递归出口，直接在image数组上对其进行操作即可

class Solution {int m,n;//矩阵的行和列int path;//记录的需要更改的值//上下左右四个位置int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {if(image[sr][sc]==color)  return image;//如果数据相同，可以直接返回m = image.size(),n = image[0].size();path = image[sr][sc];//用一个全局变量直接存放需要进行比较的值image[sr][sc] = color;dfs(image,sr,sc,color);//把坐标和数组传过去return image;}void dfs(vector<vector<int>>& image,int i,int j,int color){//无需递归出口，直接在循环里进行遍历即可for(int k = 0;k<4;k++){int x = i + dx[k],y = j + dy[k];if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==path)//注意不要过界{image[x][y] = color;dfs(image,x,y,color);}}}
};

二：岛屿数量

题目：

给一个由‘1’（陆地）和‘0’（水）组成的二维网络，请计算网格中岛屿的数量

介绍：岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成，可以假设该网络的四条边均被水包围

方法：

1：画出决策树（与之前的题目基本一致，故省略）

2：算法原理

基本思路：先进行一次遍历，找到为‘1’的位置，然后进入到递归中，将其周围的为‘1’的位置全部变为‘0’，递归回来后再将岛屿的数量加上1

dfs函数：

void dfs(grid,i,j)（grid为给出的数组，（i，j）为当前为‘1’的位置）

class Solution {//直接改变原本的数值int ret;//总共的岛屿数量int m,n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};public:int numIslands(vector<vector<char>>& grid) {m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] == '1'){dfs(grid,i,j);//将周围的的‘1’都变为‘0’ret+=1;}}} return ret;  }void dfs(vector<vector<char>>& grid,int i,int j){for(int k = 0;k<4;k++){int x = i + dx[k],y = j + dy[k];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1'){grid[x][y] = '0';dfs(grid,x,y);}}}
};

三：岛屿的最大面积

题目：

给一个大小为m*n的二进制矩阵岛屿grid

岛屿是由一些相邻的1（代表土地）构成的组合，这里的相邻要求两个1必须在水平或者竖直的四个方向上相邻，可以假设grid的四个边缘都被0（代表水）包围着

岛屿的面积是岛上值为1的单元格的数目

方法：

1：画出决策树（与之前题目基本一致，故省略）

2：算法原理

基本思路：先将数组进行遍历，若遇到1，则将其位置直接传入到dfs中，计算此块儿岛屿的面积，然后将其最后存放最大面积的ret进行比较，存放值。在dfs函数中，从传入的位置开始，上下左右四个位置进行判断，更改，然后每进行一次dfs，用来计数面积的count就加1.

class Solution {int m,n;int ret;//岛屿的最大面积int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};int count;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(),n = grid[0].size();for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(grid[i][j] == 1){count = 0;grid[i][j] = 0;dfs(grid,i,j);ret = max(ret,count);}}}return ret;}void dfs(vector<vector<int>>& grid,int i,int j){count++;for(int k = 0;k<4;k++){int x = i + dx[k],y = j + dy[k];if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){grid[x][y] = 0;//计数之后将这处的值改为0dfs(grid,x,y);}}}
};

四：被围绕的区域

题目：

给一个m*n的矩阵board，由若干字符‘X’和‘0’组成，捕获所有被围绕的区域：

（1）连接：一个单元格与水平或垂直方向上相邻的单元格

（2）区域：连接所有‘0’的单元格来形成一个区域

（3）如果您可以用‘X’单元格连接这个区域，并且区域中没有任何单元格位于board边缘，则该区域被‘X’单元格围绕

通过将输入矩阵board中的所有‘0’替换为‘X’来捕获被围绕的区域

方法：

1：画出决策树（与之前题目基本一致，故在此省略）

2：算法原理

基本思路：

解法一：直接进行深度优先遍历（过于复杂，不考虑）

解法二：正难则反（重要方法！！！）

首先把边界处理一下，边界为0的对其上下左右进行比遍历，若遇到值为0的位置，将其进行标记

（可以使用vis数组，或者将值进行改变，后续再进行复原）

class Solution {int dy[4] = {0,0,1,-1};int dx[4] = {1,-1,0,0};int m,n;public:void solve(vector<vector<char>>& board) {m = board.size(),n = board[0].size();//将与边界相连的o修改为.for(int j = 0;j<n;j++){if(board[0][j] == 'O')  dfs(board,0,j);if(board[m-1][j] == 'O') dfs(board,m-1,j);}for(int i = 0;i<m;i++){if(board[i][0] == 'O')  dfs(board,i,0);if(board[i][n-1] == 'O')  dfs(board,i ,n-1);}//复原for(int i = 0;i<m;i++){for(int j = 0;j<n;j++){if(board[i][j] == '.') board[i][j] = 'O';else if(board[i][j] == 'O')  board[i][j] = 'X';}}}void dfs(vector<vector<char>>& board,int i,int j){board[i][j] = '.';for(int k = 0;k<4;k++){int x = i+dx[k],y = j+dy[k];if(x>=0&&x<m&&y>=0&&y<n&&board[x][y] == 'O'){dfs(board,x,y);}}}
};