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))

c++

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;
    }