[Geeks for Geeks] X Total Shapes

X Total Shapes

Given a grid of n*m consisting of O’s and X’s. The task is to find the number of ‘X’ total shapes.

Note: ‘X’ shape consists of one or more adjacent X’s (diagonals not included).

  • Time : O(nm)
  • Space : O(max(n,m))
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
class Solution {
void bfs(vector<vector<char>> &grid, int sy, int sx, int n, int m) {
int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
queue<pair<int, int>> q;
grid[sy][sx] = 'O';
q.push({sy, sx});
while(!q.empty()) {
auto pos = q.front(); q.pop();
int y = pos.first, x = pos.second;
for(int i = 0; i < 4; i++) {
int ny = y + dy[i], nx = x + dx[i];
if(0 <= ny and ny < n and 0 <= nx and nx < m and grid[ny][nx] == 'X') {
grid[ny][nx] = 'O';
q.push({ny, nx});
}
}
}
}
public:
//Function to find the number of 'X' total shapes.
int xShape(vector<vector<char>> &grid) {
int res = 0, n = grid.size(), m = grid[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(grid[i][j] == 'X') {
res++;
bfs(grid, i, j, n, m);
}
}
}
return res;
}

Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/26/PS/GeeksforGeeks/x-total-shapes/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.