---
# System prepended metadata

title: 'Leetcode 695. Max Area of Island in C [C語言]'
tags: [Graph, DFS, Leetcode]

---

Leetcode 695. Max Area of Island in C [C語言]
==
###### tags: `Leetcode` `DFS` `Graph`

## Description
(Medium)
You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

![](https://i.imgur.com/iVoYwKj.png)
![](https://i.imgur.com/3Pyc2tw.png)

## 思路
一開始想到就直接尻DFS最間單，這個DFS需要兩個功能
1. 計算數字
2. 在走過的位置清為0

DFS很間單的用遞迴尻下去就好了，其中在計數的部分會使用pointer來做計算，但是pointer 在呼叫recursive得時候要的別注意一些地方
就是在main的int size=0, 會使用&size作為他的pointer丟進DFS中開始跑，我一開始寫的時候有點混亂，尤其是呼叫recursive的地方，但是可以想成是寫在DFS中的size其實已經是&size(也可以理解為size的pointer)

所以在recurdive中要使用pointer需要特別注意！！！我混亂了一陣子

## 程式
```c=
int MAX(int a, int b){
    return (a>b)?a:b;
}

void DFS(int **grid, int gridSize, int gridColSize, int r, int c, int *size){
    if(r<0 || c<0 || r>gridSize-1 || c>gridColSize-1 || grid[r][c]==0)
        return;
    if(grid[r][c]==1){
        grid[r][c]=0;
        *size += 1;
        DFS(grid, gridSize, gridColSize, r+1, c, size);
        DFS(grid, gridSize, gridColSize, r-1, c, size);
        DFS(grid, gridSize, gridColSize, r, c+1, size);
        DFS(grid, gridSize, gridColSize, r, c-1, size);
    }
}

int maxAreaOfIsland(int** grid, int gridSize, int* gridColSize){
    if(!grid || gridSize==0 || *gridColSize==0)    return 0;
    int size = 0;
    int max=0;
    for(int i=0; i< gridSize; i++){
        for(int j=0; j<*gridColSize; j++){
            if(grid[i][j]==1)   
                DFS(grid, gridSize, *gridColSize, i, j, &size);
            max = MAX(size, max);
            size = 0;
        }
    }
    return max;
}
```
![](https://i.imgur.com/GGZzyfz.png)
