Leetcode题解系列——Max Area of Island（c++版）

题目链接：695.Max Area of Island

题目大意：给出一个n*m的01矩阵，在矩阵中找出连续1所占据的最大面积。连续指的是一个单位的上下左右必须有一个为1.

注意点：

1. 矩阵不一定是方阵，在判断长度时候要注意长和宽。
2. 要注意搜索时候出现越界的情况，要判断坐标是否合理。
3. 利用深度搜索时候，可以不用visited数组来判断是否已经搜索，可以通过改变矩阵中的值来确定。

一.算法设计

显然，这是一道深度搜索图的问题，我们可以通过对于图中为1的结点作为起点来进行搜索，通过上下左右四个方向来查找是否存在1，若存在1则继续深度搜索，直到找不到任何一个1，返回遍历的个数，即sum值。

判断上下左右结点是否为1，我先初始化一个数组来生成四个方向的向量，每一个结点来分别进行四次遍历，注意是否越界。另外，当找不到1的时候要记得减回去新加的向量，回到最初的起点。

二.代码实现

class Solution {
public:
    int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

    int maxAreaOfIsland(vector<vector<int>>& grid) {
    	int result = 0;
    	for (int i = 0; i < grid.size(); ++i)
    	{
    		for (int j = 0; j < grid[0].size(); ++j)
    		{
    			if(grid[i][j] == 1){
    				int temp = dfs(i, j, grid);
    				result = max(result, temp);
    			}
    		}
    	}
        return result;
    }

    int dfs(int x, int y, vector<vector<int>>& grid){
        int sum = 1;
        grid[x][y] = 2;
    	for (int i = 0; i < 4; ++i)
    	{
            cout << "first:" << x << " " << y << endl;
    		x += dir[i][0];
            y += dir[i][1];
            if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){
                x -= dir[i][0];
                y -= dir[i][1];
                continue;
            }
            cout << x << " " << y << endl;
            if(grid[x][y] == 1){
                grid[x][y] = 2;
			    sum += dfs(x,y,grid);
                cout << x << " " << y << " " << sum << endl;
            }
            x -= dir[i][0];
            y -= dir[i][1];
    	}
        return sum;
    }
};

三.改进方法

以上我的算法跑了96ms，连名次都没有真是丢人。于是，我开始对于代码开始优化。既然我要访问四个方向的结点，那就不必来回的加减向量，而是直接进行递归。

class Solution {
public:
    int dfs(vector<vector<int>>& grid, int x, int y){
        if (x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size())
            return 0;
        if (grid[x][y] == 1){
            grid[x][y] = 2;
            return (1 + dfs(grid, x-1, y) + dfs(grid, x, y+1) + dfs(grid, x, y-1) + dfs(grid, x+1, y));
        }else
            return 0;
    }
    
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxArea = 0;
        for(int i=0; i < grid.size(); ++i)
            for (int j=0; j < grid[0].size(); ++j){
                // check if 1 is met, if yes, dfs and count the area
                if (grid[i][j] == 1)
                {
                    // we will set those visited 1 as 2, so that we dont need to store a vector<bool> visited
                    int area = dfs(grid, i, j);
                    if (area > maxArea) maxArea = area;
                }
            }        
        return maxArea;
    }
};