Mock Silver S1 · "Lost Sheep Count"

← Back to mock contests · Original problem · Suggested time: 30–60 minutes

Problem

A farm is an R×C grid of cells. Each cell is either empty (.), a fence (#), or contains a sheep (S). A "pasture" is a maximal connected region of empty-and-sheep cells connected horizontally or vertically (fences block the connection). Compute the number of pastures that contain at least one sheep.

Constraints

1 ≤ R, C ≤ 1000
Total cells ≤ 10⁶
Time limit: 2 seconds, memory: 256 MB

Sample

Input
4 5
S....
##.S#
..#.S
.S..#

Output
3

Three pastures contain at least one sheep; pastures with no sheep are not counted.

Skills this targets

Grid BFS or DFS — the bread and butter of Silver.
Avoiding stack-overflow on deep DFS at 10⁶ cells (prefer iterative BFS or increase recursion limits carefully).
Reading 2-D grid input correctly.

Self-grade after attempting

Solution sketch (open after your timer is up)

For each non-fence cell not yet visited, run BFS to mark its entire connected component visited. While exploring, track whether any cell in the component is a sheep.
If the component contained ≥1 sheep, increment the answer.
Use a vector<vector<bool>> for visited, and a queue<pair<int,int>> for BFS. Iterative beats recursive DFS at this size to avoid stack overflow.
Complexity O(R·C). At 10⁶ cells this is well under the time limit with fast I/O.
Pitfall: don't BFS into fence cells. Don't forget to check the visited flag before pushing onto the queue (or you'll get TLE from re-visiting).

#include <bits/stdc++.h>
using namespace std;
int R, C, ans = 0;
vector<string> g;
vector<vector<bool>> vis;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C;
    g.assign(R, "");
    for (int i = 0; i < R; ++i) cin >> g[i];
    vis.assign(R, vector<bool>(C, false));
    for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) {
        if (vis[r][c] || g[r][c] == '#') continue;
        bool hasSheep = false;
        queue<pair<int,int>> q;
        q.push({r, c}); vis[r][c] = true;
        while (!q.empty()) {
            auto [cr, cc] = q.front(); q.pop();
            if (g[cr][cc] == 'S') hasSheep = true;
            for (int k = 0; k < 4; ++k) {
                int nr = cr + dr[k], nc = cc + dc[k];
                if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
                if (vis[nr][nc] || g[nr][nc] == '#') continue;
                vis[nr][nc] = true;
                q.push({nr, nc});
            }
        }
        if (hasSheep) ++ans;
    }
    cout << ans << "\n";
}