LC/200variation.cpp at master · andrea-ramirez/LC · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
using namespace std;
#include <vector>

    void dfs(vector<vector<int>>& grid, int x, int y, int &count){
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0 || grid[x][y] == 2){
            return;
        }

        grid[x][y] = 2;

        if(x == 0 || x == grid.size()-1 || y == 0 || y == grid[0].size()-1){
            count++;
        }else if(x + 1 <= grid.size()-1 && grid[x+1][y] == 0){
            count++;
        }else if(x-1 >= 0 && grid[x-1][y] == 0){
            count++;
        }else if(y + 1 <= grid[0].size()-1 && grid[x][y+1] == 0){
            count++;
        }else if(y - 1 >= 0 && grid[x][y-1] == 0){
            count++;
        }

        dfs(grid,x + 1, y, count);
        dfs(grid,x - 1, y, count);
        dfs(grid,x, y + 1, count);
        dfs(grid,x, y-1, count);

    }

    int numIslands(vector<vector<int>>& grid) {
        int largestPerimeter = 0;
        int counter = 0;

        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++){
                if(grid[i][j] == 1){
                    dfs(grid,i,j,counter);
                    largestPerimeter = max(largestPerimeter,counter);
                    counter = 0;
                }
            }
        }

        return largestPerimeter;

    }

int main() {
	/*
	vector<vector<int>> grid = {{1, 0, 1, 1, 1},
 {1, 0, 1, 1, 1},
 {0, 1, 0, 1, 1}};
 */

 vector<vector<int>> grid = {{0, 0, 0, 0, 0, 0, 0},
 {0, 1, 0, 1, 1, 1, 0},
 {0, 1, 0, 1, 1, 1, 0},
 {0, 0, 1, 1, 1, 1, 0},
 {0, 0, 0, 0, 0, 0, 0}};

 cout << numIslands(grid) << endl;

  return 0;
}