This program takes a map and divides it into regions that are fully 
connected - that is, not split in half by walls, so the player can 
get anywhere in the region starting from a random point. I wrote it 
to determine if all of a dungeon level can be reached from the 
stairs, but you might find other uses for it; for example, you could 
use the results to find out where corridors need to be added to 
result in a fully connected level. Without further ado, here it is.

#include <stdio.h>

/*
 * This program divides a set of 'grids', which can be either wall or
 * floor, into connected regions. Every grid in a region is connected
 * to every other square in that region by vertical or horizontal (not
 * diagonal) connections, and not connected to grids in any other
 * region.
 *
 * We maintain a map that shows which region each grid is in. To avoid
 * iterating over the entire map every time we discover two candidate
 * regions are joined, we use a table that maps the numbers used on
 * the grid to actual region numbers. At the end of the computation,
 * we renumber the grid using this table.
 */

/* Change this to 1 to see how it works */
#define debug 0

#define MAP_WIDTH   12
#define MAP_HEIGHT  12

/*
 * Our map - 0 is wall, 1 is floor.
 *
 * We have to have a border of walls, or we may get strange errors.
 */
char grid[MAP_HEIGHT][MAP_WIDTH] = {
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0},
{0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0},
{0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
{0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0},
{0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
{0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

#define MAX_REGIONS 16
#define NO_REGION   0   /* 0 is also a valid region */

int region_grid[MAP_HEIGHT][MAP_WIDTH];
int region_map[MAX_REGIONS];
int num_regions;

/*
 * To reduce processing time, when two regions are found to connect
 * (they're really the same region), we just mark them as the same
 * without actually renumbering grids. At the end of the computation,
 * or if we run out of region numbers, we use this function to update
 * all grids to true region numbers. It also compacts the region
 * numbers, so that afterwards all region numbers 0..num_regions-1
 * are still used.
 */
void remap_regions(void)
{
    int region_index[MAX_REGIONS];
    int region_index2[MAX_REGIONS];
    int new_regions;
    int x, y;
    int i;

    new_regions = 0;

    /*
     * Iterate through the regions, and assign a new number to each
     * non-remapped region so that they'll end up compacted.
     */
    for (i = 0; i < num_regions; i++)
    {
        /* Has this region not been mapped to another region? */
        if (region_map[i] == i)
        {
            /* No, it hasn't. Assign it a new region number. */
            if (debug)
            {
                printf("Mapping region: #%i -> #%i\n", i,             
                       new_regions);
			}
            region_index[i] = new_regions++;
        }
        else
        {
            /* It's been renumbered. Check for processing errors. */
            if (region_map[region_map[i]] != region_map[i])
            {
                /*
                 * We've encountered a bug: this region has been
                 * mapped to a region that has also been mapped. Give
                 * an error and abort.
                 */
                fprintf(stderr, "Map %i->%i->%i\n", i, region_map[i],
                        region_map[region_map[i]]);
                abort();
            }

            /* Assign an in-bounds but otherwise meaningless value. */
            region_index[i] = NO_REGION;
        }
    }

    /*
     * Construct a table of the double-indirection through remapping
     * and compaction.
     */
    for (i = 0; i < num_regions; i++)
        region_index2[i] = region_index[region_map[i]];

    /* Renumber the grids, using the table we just computed. */
    for (y = 0; y < MAP_HEIGHT; y++)
        for (x = 0; x < MAP_WIDTH; x++)
            region_grid[y][x] = region_index2[region_grid[y][x]];

    /* Create a new do-nothing region mapping table. */
    for (i = 0; i < new_regions; i++)
        region_map[i] = i;

    /* Save the new number of regions. */
    num_regions = new_regions;
}

/*
 * Join two candidate regions together. This just involves updating
 * the region remapping table.
 */
void join_regions(int r1, int r2)
{
    int i;
    int r1_map, r2_map;

    /* We have to operate on primary (unremapped) regions here */
    r1_map = region_map[r1];
    r2_map = region_map[r2];

    if (debug)
    {
        printf("Joining regions #%i (%i) and #%i (%i)\n", r1, r1_map,
               r2, r2_map);
    }

    /* Modify the region mapping table. */
    for (i = 0; i < num_regions; i++)
        if (region_map[i] == r2_map)
        {
            if (debug)
            {
                printf("Mapping region #%i (%i) -> #%i\n", i,
                       region_map[i], r1_map);
            }
            region_map[i] = r1_map;
        }
}

/*
 * Create a new region.
 */
int new_region(void)
{
    int i;

    /* If we're out of regions, compact them. */
    if (num_regions >= MAX_REGIONS)
    {
        if (debug)
            printf("Remapping regions\n");
        remap_regions();
    }

    /* If we're still out of regions, we have a problem. */
    if (num_regions >= MAX_REGIONS)
    {
        fprintf(stderr, "Too many regions\n");
        abort();
    }

    /* Allocate a new region. */
    i = num_regions++;
    region_map[i] = i;

    if (debug)
        printf("New region: #%i\n", i);

    return i;
}

void find_regions(void)
{
    int x, y;
    int i;

    if (debug)
        printf("Clearing region grid\n");

    /* Clear the region grid to a valid (but meaningless) value. */
    for (y = 0; y < MAP_HEIGHT; y++)
        for (x = 0; x < MAP_WIDTH; x++)
            region_grid[y][x] = NO_REGION;

    /* Initialize the remapping table to a null map. */
    for (i = 0; i < MAX_REGIONS; i++)
        region_map[i] = i;

    /* Start with no regions. */
    num_regions = 0;

    /* Consider each grid, except the borders (leave them as walls) */
    for (y = 1; y < MAP_HEIGHT - 1; y++)
    {
        for (x = 1; x < MAP_WIDTH - 1; x++)
        {
            /* Skip wall grids. */
            if (!grid[y][x])
                continue;

            if (debug)
                printf("(%i, %i) ", x, y);

            /* 
             * Consider the possible combinations of left, above
             * grids.
             */
            if (!grid[y - 1][x])
            {
                if (!grid[y][x - 1])
                {
                    /* No floor left or above */
                    region_grid[y][x] = new_region();
                }
                else
                {
                    /* Floor left, but not above */
                    if (debug)
                    {
                        printf("Copying over #%i\n", 
                               region_grid[y][x - 1]);
                    }
                    region_grid[y][x] = region_grid[y][x - 1];
                }
            }
            else
            {
                if (!grid[y][x - 1])
                {
                    /* Floor above, but not left */
                    if (debug)
                    {
                        printf("Copying down #%i\n", 
                               region_grid[y - 1][x]);
                    }
                    region_grid[y][x] = region_grid[y - 1][x];
                }
                else
                {
                    /*
                     * Floor both left and above - are they the same 
                     * region?
                     */
                    if (region_map[region_grid[y - 1][x]] !=
                        region_map[region_grid[y][x - 1]])
                    {
                        /* No, join them. */
                        join_regions(region_grid[y - 1][x],
                                     region_grid[y][x - 1]);
                    }

                    /* They're now the same region, so copy one. */
                    if (debug)
                    {
                        printf("Copying down #%i\n", 
                               region_grid[y - 1][x]);
                    }
                    region_grid[y][x] = region_grid[y - 1][x];
                }
            }
        }
    }

    /* Do a final remapping, to make the region_grid[][] accurate. */
    remap_regions();
}

/*
 * Print our results.
 */
void print_map(void)
{
    int x, y;

    for (y = 1; y < MAP_HEIGHT - 1; y++)
    {
        for (x = 1; x < MAP_WIDTH - 1; x++)
        {
            if (grid[y][x])
            {
                printf("%c", 'A' + region_grid[y][x]);
            }
            else
                printf(" ");
        }
        printf("\n");
    }
}

int main(void)
{
    find_regions();

    print_map();

    return 0;
}