<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

344. Weed
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Andrew has visited his garden for the last time many years ago. Today's property taxes are so high, so Andrew decided to sell his garden. The land was not cultivated for a long time and now it is probably a lot of weed on it. Andrew wants to remove everything from the ground before selling. Now he wants to estimate the amount of work.

The garden has the rectangular form and is divided into N x M equal squares. Andrew's memory is phenomenal. He remembers which squares were occupied by the weed. For the purpose of simplicity, Andrew thinks that each square is either fully occupied by the weed or completely free from it. Andrew likes botany and he knows that if some square is free from the weed but at least two of its adjacent squares are occupied by the weed (two squares are adjacent if they have common side), that square will be also occupied by the weed soon. Andrew is pretty sure that during last years weed occupied every square possible. Please help Andrew to estimate how many squares is occupied by the weed.

Input
The first line of the input contains integers N and M (1 ≤ N, M ≤ 1000). Next N lines contain M characters each. Character X denotes that the corresponding square is occupied by the weed. A period character (.) denotes an empty square.

Output
Print one integer denoting the number of squares occupied by the weed after so many years.

Example(s)
sample input
sample output
3 3
X..
.X.
.X.
6

sample input
sample output
3 4
X..X
.X..
.X..
12

<|response|>
1. Abridged Problem Statement  
Given an N×M grid of cells, each cell is either occupied by weed (‘X’) or empty (‘.’). Over time, any empty cell that has at least two occupied neighbors (up, down, left, right) becomes occupied. This process continues until no more cells can change. Compute the total number of occupied cells after stabilization.

2. Key Observations  
• Monotonic growth: once a cell becomes occupied, it stays occupied.  
• Each empty cell turns occupied exactly when it first accumulates two occupied neighbors.  
• We can avoid repeated full‐grid scans by propagating the spread in a BFS‐like fashion: start from all initially occupied cells, and “push” their influence to neighbors, counting how many occupied neighbors each empty cell has. As soon as a neighbor count reaches two, that cell joins the queue as newly occupied.

3. Full Solution Approach  
a. Data structures  
   • visited[u] (size N·M): whether cell u is already occupied (initially or by spread).  
   • degree[u]: how many occupied neighbors cell u has seen so far.  
   • queue Q: cells that have just become occupied and whose neighbors we must update.  

b. Initialization  
   1. Read N, M and the grid.  
   2. For every cell initially marked ‘X’, compute its linear index u = i*M + j, set visited[u] = true, and enqueue u into Q.  

c. BFS‐style propagation  
   While Q is not empty:  
     1. Pop a cell u; increment answer counter.  
     2. Decode u into (i, j).  
     3. For each of the four neighbors v = (ni, nj) inside the grid:  
         – Increment degree[v].  
         – If degree[v] == 2 and visited[v] == false, mark visited[v] = true and enqueue v.  

d. At the end, the answer is the total number of times we popped from the queue (i.e., the total number of occupied cells).  

This runs in O(N·M) time and uses O(N·M) memory.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> t;

void read() {
    cin >> n >> m;
    t.resize(n);
    cin >> t;
}

void solve() {
    // The weed spreads to any empty cell once at least two of its four
    // neighbours are weed; this is monotone, so we just simulate the spread
    // to fixpoint with a BFS-style queue.
    //
    // degree[cell] counts how many of its neighbours are already weed. We
    // seed the queue with the initially occupied cells. Each time we pop a
    // weed cell we increment the degree of its empty neighbours; the moment
    // a not-yet-weed cell reaches degree >= 2 it becomes weed and is queued.
    // Every cell is enqueued at most once, and the answer is the number of
    // cells that were ever queued.

    int k = n * m;
    vector<bool> visited(k, false);
    vector<int> degree(k, 0);

    queue<int> q;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(t[i][j] == 'X') {
                q.push(i * m + j);
                visited[i * m + j] = true;
            }
        }
    }

    int ans = 0;
    while(!q.empty()) {
        int u = q.front();
        ans++;
        q.pop();

        int i = u / m;
        int j = u % m;
        for(auto [x, y]:
            vector<pair<int, int>>{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
            int ni = i + x;
            int nj = j + y;
            if(ni >= 0 && ni < n && nj >= 0 && nj < m) {
                degree[ni * m + nj]++;
                if(degree[ni * m + nj] >= 2 && !visited[ni * m + nj]) {
                    q.push(ni * m + nj);
                    visited[ni * m + nj] = true;
                }
            }
        }
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    grid = [input().rstrip('\n') for _ in range(N)]

    total = N * M
    visited = [False] * total  # True if cell u has weed
    degree  = [0] * total      # Number of occupied neighbors

    Q = deque()
    # Enqueue initially occupied cells
    for i in range(N):
        for j in range(M):
            if grid[i][j] == 'X':
                u = i * M + j
                visited[u] = True
                Q.append(u)

    answer = 0
    # Four directions: up, down, left, right
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]

    # BFS-like propagation
    while Q:
        u = Q.popleft()
        answer += 1
        i, j = divmod(u, M)
        for di, dj in dirs:
            ni, nj = i + di, j + dj
            if 0 <= ni < N and 0 <= nj < M:
                v = ni * M + nj
                degree[v] += 1
                # When an empty cell accumulates 2 occupied neighbors
                if degree[v] == 2 and not visited[v]:
                    visited[v] = True
                    Q.append(v)

    print(answer)

if __name__ == "__main__":
    main()
```