NTHU Introduction to Programming: Assignment 2

/* Michael Hartman
 * NTHU Spring 2015
 * X1030035
 * Introduction to programming
 */
#include <stdio.h>
#include <stdlib.h>

typedef struct Maze
 {
    char ** arr;
    int rows, cols;
 } maze;

typedef struct Solution
 {
    int size, maxSize;
    int * arr;
 } solution;

int readDimensions ( int * c, int * r )
 {
    if ( scanf ( "%d %d", c, r ) != 2 || c <= 0 || r <= 0 )
        return 0;
    return 1;
 }

void initMaze ( maze * m )
 {
    int i;
    m -> arr = ( char ** ) malloc ( m -> rows * sizeof ( char * ) );
    for ( i = 0; i < m -> rows; ++ i )
        m -> arr[i] = ( char * ) malloc ( m -> cols * sizeof( char ) );
 }

void initSolution ( solution * s )
 {
    s -> size = 0;
    s -> maxSize = 10;
    s -> arr = ( int * ) malloc ( s -> maxSize * sizeof ( int ) );
 }

void reallocSolution ( solution * s )
 {
    s -> maxSize *= 2;
    s -> arr = ( int * ) realloc ( s -> arr, s -> maxSize * sizeof ( int ) );
 }

void pushSolution ( int i, solution * s )
 {
    if ( s -> size == s -> maxSize )
        reallocSolution ( s );
    s -> arr[ s-> size ++ ] = i;
 }

void freeSolution ( solution * s )
 {
    free ( s -> arr );
    s -> arr = NULL;
 }

void printSolution ( solution * s )
 {
    int i;
    for ( i = s -> size - 1; i > 2; i -= 2 )
        printf ( "(%d,%d)->", s -> arr[i-1], s -> arr[i] );
    printf ( "(%d,%d)\n", s -> arr[0], s -> arr[1] );
 }

void freeMaze ( maze * m )
 {
    int i;
    for ( i = 0; i < m -> rows; ++ i )
        free ( m -> arr[i] );
    free ( m -> arr );
    m -> arr = NULL;
 }

int readMaze ( maze * m )
 {
    int i, j;
    getchar();
    for ( i = 0; i < m -> rows; ++ i )
     {
        for ( j = 0; j < m -> cols; ++ j )
            m -> arr[i][j] = getchar();
        getchar();
     }
    return 1;
 }

void printMaze ( maze * m )
 {
    int i, j;
    for ( i = 0; i < m -> rows; ++ i )
     {
        printf ( "\n" );
        for ( j = 0; j < m -> cols; ++j )
            printf ( "%c", m -> arr[i][j] );
     }

    printf ( "\n" );
 }

int pushCoords ( int c, int r, solution * s )
 {
    pushSolution ( c, s );
    pushSolution ( r, s );
    return 1;
 }

int solveMaze ( maze * m, solution * s, int c, int r )
 {
    if ( c < 0 || r < 0 || c >= m -> cols || r >= m -> rows )
        return 0;
    if ( m -> arr[r][c] == '1' || m -> arr[r][c] == '2' || m -> arr[r][c] == '3' )
        return 0;
    m -> arr[r][c] = '2';
    if ( c == m -> cols - 1 && r == m -> rows - 1 )
        return pushCoords ( c, r, s );
    if ( solveMaze ( m, s, c, r - 1 ) )
        return pushCoords ( c, r, s );
    if ( solveMaze ( m, s, c + 1, r ) )
        return pushCoords ( c, r, s);
    if ( solveMaze ( m, s, c, r + 1 ) )
        return pushCoords ( c, r, s );
    if ( solveMaze ( m, s, c - 1, r ) )
        return pushCoords ( c, r, s );
    m -> arr[r][c] = '3';
    return 0;
 }

int main ( int argc, char ** argv )
 {
    maze m;
    solution s;
    int i, j;
    if ( ! readDimensions ( & m . cols, & m . rows ) )
     {
        printf ("Dimensions reading failed!\n");
        return 1;
     }

    initMaze ( & m );
    readMaze ( & m );
    initSolution ( & s );

    if ( solveMaze ( & m, & s, 0, 0 ) )
        printSolution ( & s );
    else
        printf ( "No way out!\n" );

    freeMaze ( & m );
    freeSolution ( & s );
    return 0;
 }