Skip to content

Instantly share code, notes, and snippets.

@v1k22
Created June 11, 2019 12:07
Show Gist options
  • Select an option

  • Save v1k22/b4475abe22be195085190071f8dc45c5 to your computer and use it in GitHub Desktop.

Select an option

Save v1k22/b4475abe22be195085190071f8dc45c5 to your computer and use it in GitHub Desktop.
black shapes interview bit (using c++ lambda for recursive dfs)
int n;
int m;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int Solution::black(vector<string> &A) {
n = A.size();
if (n == 0) return 0;
m = A[0].length();
vector < vector < bool > > visited(n, vector < bool > (m, false));
function < void (int, int) > dfs;
dfs = [&](int u, int v) -> void {
visited[u][v] = true;
for (int i = 0; i < 4; i++) {
int pp = u + dx[i];
int qq = v + dy[i];
if (pp >= 0 && qq >= 0 && pp < n && qq < m)
if (!visited[pp][qq] && A[pp][qq] == 'X')
dfs(pp, qq);
}
};
int ans = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
if (!visited[i][j] && A[i][j] == 'X') {
ans++;
dfs(i, j);
}
}
return ans;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment