The paint-bucket tool in an image editor spreads to every square it can reach. Count them.
What to build
A flood fill that counts the squares reachable from S.
Requirements
- Moves go up, down, left or right, and never onto a wall
#. - Count the start square too.
- Never count a square twice.
Input
The first line has R and C. Each of the next R lines has C characters: S (exactly one), . or #.
Output
The number of reachable squares.
Constraints
1 ≤ R, C ≤ 20.
Example
Input:
3 4
S..#
.#..
...#
Output:
9
Why it works
Each square is marked the first time it is reached, so it is counted once and never explored again. Each of the R × C squares does a constant amount of work.
Examples
Example 1 · Input
3 4 S..# .#.. ...#
Expected output
9
Example 2 · Input
1 1 S
Expected output
1
Hints
Hint 1
A recursive function can visit a square, mark it, and call itself on the four neighbours.
Hint 2
Check the bounds first, then whether the square is a wall or already visited.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
char grid[20][22];
int seen[20][20];
int R, C;
int fill(int r, int c) {
if (r < 0 || r >= R || c < 0 || c >= C) return 0;
if (grid[r][c] == '#' || seen[r][c]) return 0;
seen[r][c] = 1;
return 1 + fill(r - 1, c) + fill(r + 1, c) + fill(r, c - 1) + fill(r, c + 1);
}
int main(void) {
scanf("%d %d", &R, &C);
for (int r = 0; r < R; r++) scanf("%21s", grid[r]);
int answer = 0;
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (grid[r][c] == 'S') answer = fill(r, c);
printf("%d\n", answer);
return 0;
}