# Floodfill

## Problem:

Given an $N \times N, (1 \le N \le 1000)$ matrix of ‘#’s and ‘O’s, find the number of “spots” of Os in the matrix, where a spot consists of all Os that are adjacent along some edge.

## Input (file.in):

Line $1$: A single integer, $N$.
Lines $2 \ldots N+1$: $N$ characters that represent a row of the matrix.

## Output (file.out):

Line $1$: The number of spots of Os.

## Solution:

/*
* Example Floodfill using Recursion
* Albert Gural
*/

#include <fstream>

using namespace std;
FILE *fin  = fopen("file.in",  "r");
FILE *fout = fopen("file.out", "w");
int field[1000][1000], N, cur = 1;
char c;

// Floodfill Recursion function takes a position (x, y)
// and fills it and surrounding elements with f.
void flood(int x, int y, int f) {
if(x < 0 || y < 0 || x >= N || y >= N) return;
if(field[x][y] != 0) return;
field[x][y] = f;

// Recursively look at adjacent elements.
flood(x-1, y, f);
flood(x+1, y, f);
flood(x, y-1, f);
flood(x, y+1, f);
}

int main () {
fscanf(fin, "%d", &N);

// Fill our field with -1's or 0's based on input.
for(int a = 0; a < N; a++) {
for(int b = 0; b < N; b++) {
fscanf(fin, "%c", &c);
if(c == '\n') fscanf(fin, "%c", &c);
field[a][b] = (c == '#')? -1:0;
}
}

// For each element, if not already flooded, flood it.
// Increment cur to indicate current flood number.
for(int a = 0; a < N; a++) {
for(int b = 0; b < N; b++) {
if(field[a][b] == 0) {
flood(a, b, cur);
cur++;
}
}
}

// The number of distinct floods is given by (cur-1).
fprintf(fout, "%d\n", cur - 1);
return 0;
}