Today I have done leetcode's May LeetCoding Challenge with cpp.

May LeetCoding Challenge 21

Description

Shortest Bridge

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

• n == grid.length == grid[i].length
• 2 <= n <= 100
• grid[i][j] is either 0 or 1.
• There are exactly two islands in grid.

Solution

class Solution {
  const int moves[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
  using pi = pair<int, int>;
public:
  int shortestBridge(vector<vector<int>>& grid) {
    int n = grid.size();
    queue<pi> q;
    for(int i = 0; i < n && q.empty(); ++i) {
      for(int j = 0; j < n && q.empty(); ++j) {
        if(grid[i][j]) {
          q.push({i, j});
          grid[i][j] = 2;
        }
      }
    }
    while(q.size()) {
      auto [row, col] = q.front();
      q.pop();
      grid[row][col] = 2;
      for(int m = 0; m < 4; ++m) {
        int newRow = row + moves[m][0];
        int newCol = col + moves[m][1];
        if(newRow < 0 || newCol < 0 || newRow >= n || newCol >= n) continue;
        if(grid[newRow][newCol] != 1) continue;
        q.push({newRow, newCol});
        grid[newRow][newCol] = 2;
      }
    }

    for(int i = 0; i < n; ++i) {
      for(int j = 0; j < n; ++j) {
        if(grid[i][j] == 2) {
          q.push({i, j});
        }
      }
    }

    int answer = 0;
    while(q.size()) {
      int s = q.size();
      for(int _ = 0; _ < s; ++_) {
        auto [row, col] = q.front();
        q.pop();
        for(int m = 0; m < 4; ++m) {
          int newRow = row + moves[m][0];
          int newCol = col + moves[m][1];
          if(newRow < 0 || newCol < 0 || newRow >= n || newCol >= n) continue;
          if(grid[newRow][newCol] == 2) continue;
          if(grid[newRow][newCol] == 1) return answer;
          q.push({newRow, newCol});
          grid[newRow][newCol] = 2;
        }
      }
      answer += 1;
    }
    return -1;
  }
};

// Accepted
// 97/97 cases passed (48 ms)
// Your runtime beats 80.51 % of cpp submissions
// Your memory usage beats 91.3 % of cpp submissions (18.6 MB)