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

320. The Influence of the Mafia
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



The problem with zones of influence was finally solved during the recent Berland mafia meeting. Berland was represented as a rectangle of N x M squares. All squares were divided between the mafia leaders. Each leader got a connected region of squares, i.e. it is possible to get from any square of the region to any other by making moves only across the squares of this region. Four types of moves are allowed: up, down, left and right.

Each leader was assigned a number from 0 to 9, it is allowed for two different leaders to have the same number. The leaders decided to create a map of Berland where each square has the number of the leader who owes it. The secretary was able to assign leaders with numbers in such a way that no two bordering regions on the map have the same number. The valiant Berland police seized the map with the numbers. And now the chief of the police wants to know the degree of the mafia influence in Berland.

He introduced following definitions:

A leader is called big if he possesses K or more squares.

A square is called dangerous if it is controlled by a big leader or if there exists such big leader that it is impossible to get out of Berland (i.e. to get to a square on the border of the country) without visiting a square controlled by this leader. Allowed moves: up, down, left and right.

The chief of the police wants to know the number of dangerous squares in the country. He decided to ask his valiant programmers to solve this important task.

Input
The first line of the input contains integer numbers N, M and K (1≤ N, M≤ 500; 1≤ K≤ 250000). The map created by the secretary follows. The map is written in the form of N lines with M numbers from 0 to 9 in each line. Numbers in a line are written one after another without spaces.

Output
Write to the output the number of dangerous squares in the country.

Example(s)
sample input
sample output
7 6 4
200320
011022
018100
018111
201191
020011
002020
14



Note
There are two big leaders in the country (both are marked with the number 1, one has 4 squares, another has 9 squares). There is one more dangerous square (marked with the number 9) besides the regions in possession of big leaders. Note that squares marked with the number 8 are not dangerous, as they do not satisfy the definition of a dangerous square.

<|response|>
## 1. Abridged problem statement

We have an `N × M` grid of digits `0..9`.

Each mafia leader owns one 4-connected region of cells. Different neighboring regions always have different digits, so each maximal connected component of equal digits is one leader’s territory.

A leader is **big** if its region has at least `K` cells.

A cell is **dangerous** if:

1. it belongs to a big leader, or
2. there exists a big leader such that every path from this cell to the border of the grid must pass through that big leader’s region.

Find the number of dangerous cells.

Constraints:

```text
1 ≤ N, M ≤ 500
1 ≤ K ≤ 250000
```

---

## 2. Key observations needed to solve the problem

### Observation 1: Equal-digit connected components are leaders

Since two neighboring regions cannot have the same digit, every maximal 4-connected component of equal digits corresponds to exactly one mafia leader.

So the first step is to compress the grid into components.

For every component we need:

- its size,
- whether it touches the border,
- which other components are adjacent to it.

---

### Observation 2: Build a graph of components

After compression:

- each component becomes a graph vertex,
- two vertices are connected if their regions touch in the grid,
- add one extra virtual vertex called `OUTSIDE`,
- connect `OUTSIDE` to every component that touches the border.

Now escaping from a cell to the border is equivalent to reaching `OUTSIDE` in this component graph.

---

### Observation 3: Dangerous non-big components are separated by big articulation points

Consider a non-big component `C`.

It is dangerous if there exists a big component `B` such that every path from `C` to `OUTSIDE` passes through `B`.

In graph terms:

> Removing `B` disconnects `C` from `OUTSIDE`.

That means `B` is an articulation point separating `C` from `OUTSIDE`.

---

### Observation 4: Tarjan DFS detects such separations

Root a DFS at `OUTSIDE`.

For a DFS tree edge:

```text
u -> v
```

if:

```text
low[v] >= tin[u]
```

then the subtree of `v` cannot reach an ancestor of `u` without passing through `u`.

Therefore, if `u` is a big component, every component in `v`’s DFS subtree is dangerous.

---

### Observation 5: Mark whole DFS subtrees efficiently

DFS subtrees occupy contiguous intervals in DFS discovery order.

If component `v` has subtree interval:

```text
[tin[v], tout[v]]
```

then we can mark the whole subtree using a difference array:

```text
diff[tin[v]] += 1
diff[tout[v] + 1] -= 1
```

After prefix sums, a component is marked if its DFS entry time has positive coverage.

---

## 3. Full solution approach based on the observations

### Step 1: Compress the grid

Run BFS/DFS over the grid.

For every unvisited cell:

1. create a new component,
2. flood-fill all adjacent cells with the same digit,
3. assign them the same component ID,
4. count the component size,
5. record whether it touches the border.

---

### Step 2: Build the component graph

Scan all neighboring cell pairs:

- right neighbor,
- down neighbor.

If two neighboring cells belong to different components, add an undirected edge between those two components.

To avoid duplicate edges, store encoded edges, sort them, and remove duplicates.

Then add virtual vertex `OUTSIDE`.

For every border-touching component, add an edge:

```text
component -- OUTSIDE
```

---

### Step 3: Mark big components

A component is big if:

```text
component_size >= K
```

All cells inside big components are automatically dangerous.

---

### Step 4: Run Tarjan DFS from `OUTSIDE`

Compute:

- `tin[u]`: DFS discovery time,
- `low[u]`: smallest discovery time reachable from `u`’s subtree using at most one back edge.

For every DFS tree edge `u -> v`, after finishing `v`:

```text
if low[v] >= tin[u] and u is big:
    mark subtree of v as dangerous
```

This means all paths from that subtree to `OUTSIDE` must pass through big component `u`.

---

### Step 5: Count answer

For every component:

- if it is big, add its size,
- else if it was marked by some big articulation component, add its size.

---

### Complexity

Let:

```text
S = N × M
```

The number of components and component-graph edges is `O(S)`.

Therefore:

```text
Time complexity:  O(S log S)
```

The `log S` factor comes from sorting graph edges.

```text
Memory complexity: O(S)
```

---

## 4. C++ Solution

```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, k;
vector<string> grid;

vector<vector<int>> comp_id;
vector<int> comp_size;
vector<char> comp_touches_border;
vector<set<int>> comp_neighbours;

void read() {
    cin >> n >> m >> k;
    grid.resize(n);
    for(int i = 0; i < n; i++) {
        cin >> grid[i];
    }
}

const int di[4] = {-1, 0, 1, 0};
const int dj[4] = {0, 1, 0, -1};

void label_zones() {
    comp_id.assign(n, vector<int>(m, -1));
    comp_size.clear();
    comp_touches_border.clear();
    comp_neighbours.clear();

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(comp_id[i][j] != -1) {
                continue;
            }

            int cid = comp_size.size();
            comp_size.push_back(0);
            comp_touches_border.push_back(0);
            comp_neighbours.emplace_back();

            char color = grid[i][j];
            queue<pair<int, int>> q;
            q.push({i, j});
            comp_id[i][j] = cid;

            while(!q.empty()) {
                auto [x, y] = q.front();
                q.pop();
                comp_size[cid]++;
                if(x == 0 || x == n - 1 || y == 0 || y == m - 1) {
                    comp_touches_border[cid] = 1;
                }

                for(int d = 0; d < 4; d++) {
                    int nx = x + di[d], ny = y + dj[d];
                    if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
                        continue;
                    }

                    if(grid[nx][ny] == color) {
                        if(comp_id[nx][ny] == -1) {
                            comp_id[nx][ny] = cid;
                            q.push({nx, ny});
                        }
                    } else if(comp_id[nx][ny] != -1) {
                        comp_neighbours[cid].insert(comp_id[nx][ny]);
                        comp_neighbours[comp_id[nx][ny]].insert(cid);
                    }
                }
            }
        }
    }
}

vector<char> dominated_by_big_zone(const vector<char>& is_big) {
    int num_comps = comp_size.size();
    int outside = num_comps;
    int V = num_comps + 1;

    vector<vector<int>> adj(V);
    for(int c = 0; c < num_comps; c++) {
        for(int u: comp_neighbours[c]) {
            adj[c].push_back(u);
        }
        if(comp_touches_border[c]) {
            adj[c].push_back(outside);
            adj[outside].push_back(c);
        }
    }

    vector<int> disc(V, -1), low(V, 0), in_t(V, 0);
    vector<int> dom(V + 2, 0);
    vector<tuple<int, int, int>> st;
    st.reserve(V);
    int timer = 0;

    st.emplace_back(outside, 0, -1);
    disc[outside] = low[outside] = in_t[outside] = timer++;

    while(!st.empty()) {
        auto& [u, it, p] = st.back();
        if(it < (int)adj[u].size()) {
            int v = adj[u][it++];
            if(v == p) {
                continue;
            }

            if(disc[v] == -1) {
                disc[v] = low[v] = in_t[v] = timer++;
                st.emplace_back(v, 0, u);
            } else {
                low[u] = min(low[u], disc[v]);
            }
        } else {
            int u_low = low[u], u_in = in_t[u], u_out = timer - 1, parent = p;
            st.pop_back();
            if(parent == -1) {
                continue;
            }

            low[parent] = min(low[parent], u_low);
            if(u_low >= disc[parent] && parent < num_comps && is_big[parent]) {
                dom[u_in] += 1;
                dom[u_out + 1] -= 1;
            }
        }
    }

    for(int t = 1; t < timer; t++) {
        dom[t] += dom[t - 1];
    }

    vector<char> result(num_comps, 0);
    for(int c = 0; c < num_comps; c++) {
        result[c] = dom[in_t[c]] > 0;
    }
    return result;
}

void solve() {
    // If we group same-color 4-connected cells into zones, the resulting
    // structure is planar. A cell is dangerous iff it is part of a big zone
    // (size >= K) or lies strictly inside a face of some big zone, i.e.
    // there is a big zone X such that every escape path from the cell to
    // the border passes through X. Equivalently, X is an articulation point
    // separating the cell's zone from a virtual OUTSIDE node in the zone
    // adjacency graph.
    //
    // We flood fill once to label every zone with a component id and to
    // record its size, whether it touches the border, and the set of
    // neighbouring zones. Then we build the zone graph with an extra
    // OUTSIDE node joined to every border-touching zone and run Tarjan's
    // articulation point algorithm rooted at OUTSIDE. Whenever a DFS-tree
    // child v of u finishes with low[v] >= disc[u] and u is a big zone, u
    // cuts the entire subtree of v from OUTSIDE, so every zone in v's
    // subtree is dangerous. We mark each such subtree as a +1/-1 range on
    // the Euler-tour index and prefix-sum at the end.

    label_zones();

    int num_comps = comp_size.size();
    vector<char> is_big(num_comps, 0);
    for(int c = 0; c < num_comps; c++) {
        is_big[c] = comp_size[c] >= k;
    }

    auto dominated = dominated_by_big_zone(is_big);

    int ans = 0;
    for(int c = 0; c < num_comps; c++) {
        if(is_big[c] || dominated[c]) {
            ans += comp_size[c];
        }
    }
    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();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys


def solve():
    data = sys.stdin.read().strip().split()

    if not data:
        return

    n = int(data[0])
    m = int(data[1])
    k = int(data[2])

    rows = data[3:3 + n]

    # Flatten grid.
    # Cell (r, c) has index r * m + c.
    flat = ''.join(rows)
    total = n * m

    # comp_id[cell] = component id of this cell.
    comp_id = [-1] * total

    # Size of each component.
    comp_size = []

    # Whether each component touches the grid border.
    touches_border = []

    # ------------------------------------------------------------
    # Step 1: Flood-fill equal-digit connected components.
    # ------------------------------------------------------------

    for start in range(total):
        if comp_id[start] != -1:
            continue

        cid = len(comp_size)
        color = flat[start]

        comp_id[start] = cid
        stack = [start]

        size = 0
        border = False

        while stack:
            v = stack.pop()
            size += 1

            r = v // m
            c = v % m

            if r == 0 or r == n - 1 or c == 0 or c == m - 1:
                border = True

            # Up.
            if r > 0:
                to = v - m
                if flat[to] == color and comp_id[to] == -1:
                    comp_id[to] = cid
                    stack.append(to)

            # Down.
            if r + 1 < n:
                to = v + m
                if flat[to] == color and comp_id[to] == -1:
                    comp_id[to] = cid
                    stack.append(to)

            # Left.
            if c > 0:
                to = v - 1
                if flat[to] == color and comp_id[to] == -1:
                    comp_id[to] = cid
                    stack.append(to)

            # Right.
            if c + 1 < m:
                to = v + 1
                if flat[to] == color and comp_id[to] == -1:
                    comp_id[to] = cid
                    stack.append(to)

        comp_size.append(size)
        touches_border.append(border)

    comps = len(comp_size)
    outside = comps
    vertices = comps + 1

    # ------------------------------------------------------------
    # Step 2: Build component graph.
    # ------------------------------------------------------------

    # Store encoded edges a * comps + b, where a < b.
    edge_codes = []

    for r in range(n):
        base = r * m

        for c in range(m):
            idx = base + c
            a = comp_id[idx]

            # Right neighbor.
            if c + 1 < m:
                b = comp_id[idx + 1]
                if a != b:
                    x, y = (a, b) if a < b else (b, a)
                    edge_codes.append(x * comps + y)

            # Down neighbor.
            if r + 1 < n:
                b = comp_id[idx + m]
                if a != b:
                    x, y = (a, b) if a < b else (b, a)
                    edge_codes.append(x * comps + y)

    edge_codes.sort()

    adj = [[] for _ in range(vertices)]

    # Add unique component-component edges.
    prev = None

    for code in edge_codes:
        if code == prev:
            continue

        prev = code

        a = code // comps
        b = code % comps

        adj[a].append(b)
        adj[b].append(a)

    # Connect border-touching components to OUTSIDE.
    for c in range(comps):
        if touches_border[c]:
            adj[c].append(outside)
            adj[outside].append(c)

    # ------------------------------------------------------------
    # Step 3: Determine big components.
    # ------------------------------------------------------------

    is_big = [size >= k for size in comp_size]

    # ------------------------------------------------------------
    # Step 4: Tarjan DFS from OUTSIDE.
    # ------------------------------------------------------------

    tin = [-1] * vertices
    low = [0] * vertices

    # Difference array over DFS order.
    diff = [0] * (vertices + 2)

    timer = 0

    tin[outside] = low[outside] = timer
    timer += 1

    # Stack frame:
    # [current_vertex, next_neighbor_index, parent]
    stack = [[outside, 0, -1]]

    while stack:
        u, it, parent = stack[-1]

        if it < len(adj[u]):
            v = adj[u][it]

            # Advance iterator of the current frame.
            stack[-1][1] += 1

            # Ignore the tree edge back to parent.
            if v == parent:
                continue

            if tin[v] == -1:
                # Tree edge.
                tin[v] = low[v] = timer
                timer += 1
                stack.append([v, 0, u])
            else:
                # Back edge.
                low[u] = min(low[u], tin[v])

        else:
            # Finish vertex u.
            u_in = tin[u]

            # All vertices discovered since u_in belong to u's DFS subtree.
            u_out = timer - 1

            u_low = low[u]

            stack.pop()

            if parent == -1:
                continue

            # Propagate low-link value to parent.
            low[parent] = min(low[parent], u_low)

            """
            If parent is a big component and the subtree of u cannot reach
            above parent, then every path from that subtree to OUTSIDE
            must pass through parent.
            """
            if parent < comps and is_big[parent] and u_low >= tin[parent]:
                diff[u_in] += 1
                diff[u_out + 1] -= 1

    # Prefix sum of difference array.
    for i in range(1, timer):
        diff[i] += diff[i - 1]

    # ------------------------------------------------------------
    # Step 5: Count dangerous cells.
    # ------------------------------------------------------------

    answer = 0

    for c in range(comps):
        dominated_by_big = diff[tin[c]] > 0

        if is_big[c] or dominated_by_big:
            answer += comp_size[c]

    print(answer)


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