Vietnamese Maze

README.md

Simple solution to the problem showed in https://neil.fraser.name/news/2013/03/16/ The goal is to find the number of enclosed areas in a grid made of diagonal lines.

Usage

The program reads the maze from the standard input. The first line read must be the dimension of the maze, and the following lines are the maze cells, made of / (or 0) and \ (or 1).

Examples

No enclosed areas:

./maze
2,2
\\
\\
#..#...
.#..#..
..#..#.
#..#..#
.#..#..
..#..#.
...#..#
number of enclosed areas = 0

One enclosed area:

./maze
3,3
//\
\\/    
/\\
...#..#...
..#..#.#..
.#..#...#.
#..#.....#
.#..#...#.
..#..#.#..
...#..#...
..#.#..#..
.#...#..#.
#.....#..#
6, 1
number of enclosed areas = 1

More:

./maze
5,5
/\/\\
\/\//
\\\\\
/////
\\///
...#.....#..#...
..#.#...#.#..#..
.#...#.#...#..#.
#.....#.....#..#
.#...#.#...#..#.
..#.#...#.#..#..
#..#..#..#..#...
.#..#..#..#..#..
..#..#..#..#..#.
...#..#..#..#..#
..#..#..#..#..#.
.#..#..#..#..#..
#..#..#..#..#..#
.#..#...#..#..#.
..#..#.#..#..#..
...#..#..#..#...
number of enclosed areas = 3

Makefile

maze : maze.o
	gcc $^ -o $@

%.o : %.c
	gcc -std=c99 -Wall -Werror $^ -c -o $@

maze.c

#include <string.h>
#include <stdio.h>
#include <stdbool.h>
#include <assert.h>
#include <stdlib.h>

typedef enum {
    UNVISITED = 0,
    VISITED,
    ENCLOSED,
    OPEN
} State;

bool is_enclosed(void* grid_ptr, int x, int y, int width, int height) {
    State (*grid)[height] = grid_ptr;

    if (x < 0 || x >= width || y < 0 || y >= height
        || grid[x][y] == OPEN) {
        return false;
    } else if (grid[x][y] == VISITED || grid[x][y] == ENCLOSED) {
        return true;
    } else {
        grid[x][y] = VISITED;
        
        bool r = is_enclosed(grid_ptr, x, y - 1, width, height)
              && is_enclosed(grid_ptr, x, y + 1, width, height)
              && is_enclosed(grid_ptr, x - 1, y, width, height)
              && is_enclosed(grid_ptr, x + 1, y, width, height);

        grid[x][y] = r ? ENCLOSED : OPEN;

        return r;
    }
}

#define FACTOR 3

int main() {
    // read size
    int width, height;
    if (fscanf(stdin, "%d,%d\n", &width, &height) != 2) {
        fprintf(stderr, "error: invalid size specifiers\n");   
        exit(EXIT_FAILURE);
    };

    // fill the grid by reading from stdin
    State grid[FACTOR*width + 1][FACTOR*height + 1];
    memset(grid, UNVISITED, sizeof(grid));

    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            switch (getchar()) {
                case '/':
                case '0':
                    for (int k = 0; k <= FACTOR; k++) {
                        grid[FACTOR*x + k][FACTOR*y + FACTOR - k] = VISITED;
                    }
                    break;
                case '\\':
                case '1':
                    for (int k = 0; k <= FACTOR; k++) {
                        grid[FACTOR*x + k][FACTOR*y + k] = VISITED;
                    }
                    break;
                default:
                fprintf(stderr, "error: invalid character\n");
                exit(EXIT_FAILURE);

            }
        }

        if (getchar() != '\n') {
            fprintf(stderr, "error: wrong line length\n");
            exit(EXIT_FAILURE);
        }
    }


    // print the resampled maze
    for (int y = 0; y < FACTOR*height + 1; y++) {
        for (int x = 0; x < FACTOR*width + 1; x++) {
            printf("%c", (grid[x][y] == VISITED ? '#' : '.'));
        }
        printf("\n");
    }

    // count the enclosed areas
    int cnt = 0;

    for (int y = 1; y < FACTOR*height; y++) {
        for (int x = 1; x < FACTOR*width; x++) {
            if (grid[x][y] == UNVISITED
                    && is_enclosed(grid, x, y, FACTOR*width + 1, FACTOR*height + 1)) {
                cnt += 1;
            }
        }
    }

    printf("number of enclosed areas = %d\n", cnt);

	return 0;
}