Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created January 20, 2018 18:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/f796b94821a1c13d70b37bdce9c52e73 to your computer and use it in GitHub Desktop.
Save jianminchen/f796b94821a1c13d70b37bdce9c52e73 to your computer and use it in GitHub Desktop.
Breadth first search - count connected elements - peer code using C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct vec2i {
int x, y;
};
void bfs(vector<vector<int>>& binaryMatrix, int rows, int cols, vec2i pos) {
deque<vec2i> q;
q.push_back(pos);
while (!q.empty()) {
vec2i cur = q.front();
q.pop_front();
if (cur.x >= 0 && cur.x < rows && cur.y >= 0 && cur.y < cols) {
int& value = binaryMatrix[cur.x][cur.y];
if (value == 1) {
value = 0;
// Add neighbours:
q.push_back(vec2i{cur.x - 1, cur.y}); // Left
q.push_back(vec2i{cur.x + 1, cur.y}); // Right
q.push_back(vec2i{cur.x, cur.y - 1}); // Top
q.push_back(vec2i{cur.x, cur.y + 1}); // Top
}
}
}
}
int getNumberOfIslands( const vector<vector<int>>& binaryMatrix )
{
auto binaryMatrixMutable = binaryMatrix;
int num_islands = 0;
int rows = binaryMatrix.size();
int cols = (rows ? binaryMatrixMutable[0].size() : 0);
for (int row = 0; row < rows; ++row) {
for (int col = 0; col < cols; ++col) {
int value = binaryMatrixMutable[row][col];
if (value == 1) {
bfs(binaryMatrixMutable, rows, cols, vec2i{row, col});
++num_islands;
}
}
}
return num_islands;
}
int main() {
return 0;
}
@jianminchen
Copy link
Author

Ask the peer about C++ using struct, instead of using array
void f(int arr[256]) {
cerr << "Size of the parameter: " << sizeof(arr) << "\n";
} // empty array will return size of 8.

int main() {
f(nullptr);
return 0;
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment