[LeetCode | C++] August LeetCoding Challenge 2021 — Week1 Making A Large Island(1st, August)

📃 Problem

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/613/week-1-august-1st-august-7th/3835/

💡 Check Point

1. Consider how to avoid time limit exceed — Using DFS & Memorize the number that indicates the connection number of each island.

2. Consider how to change the value (0 to 1) of grid.

👩‍💻 My Solution

#define MAX 501
class Solution {
public:
  int visited[MAX][MAX];
  int count, visitCount = 0;
  int largestIsland(vector<vector<int> >& grid) {
    int answer = 0;
    int n = grid.size();
    int m = grid[0].size();
    memset(visited, 0, sizeof(visited));

    for(int cx = 0; cx < n; cx++) {
        for(int cy = 0; cy < m; cy++) {
          if(grid[cx][cy] == 1) {
            continue;
        }
        grid[cx][cy] = 1;
        count = 0;
        visitCount++;
        dfs(cx, cy, grid);
        answer = max(answer, count);
        grid[cx][cy] = 0;
    } 
  }
  return answer == 0 ? n*m : answer;
}
void dfs(int x, int y, vector<vector<int> > &grid) {
  int dx[4] = {-1, 0, 1, 0};
  int dy[4] = {0, 1, 0, -1};
  int n = grid.size();
  int m = grid[0].size();
  if(visited[x][y] == visitCount) {
    return;
  }
  visited[x][y] = visitCount;
  count++;
  for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];

    if(nx < 0 || ny < 0|| nx > n-1 || ny > n-1) {
        continue;
    }

    if(visited[nx][ny] < visitCount && grid[nx][ny]) { 
        dfs(nx, ny, grid);
    }
  }
 }
};