driver.c

#include

#include

#include

#include "paintRoom.h"

RoomData read2DArray( const char* name );

void print2DArray( RoomData room );

void free2DArray( RoomData room );

/* change the following constants to add/remove some cases for testing */

const int numFiles = 8;

const char *defaultFilenames[] = { "room-Small01.txt", "room-Small02.txt", "room-Medium01.txt", "room-Medium02.txt", "room-Long01.txt", "room-Long02.txt", "room-Large01.txt", "room-Large02.txt" };

const bool enableFilenames[] = { true , true , true , true , true , true , true , true };

/* DO NOT MODIFY THIS FILE */

int main( int argc, char *argv[] )

{

int i;

RoomData room;

printName( );

printf("Running default test files: ");

for( i=0; i

{

if( enableFilenames[i] )

{

printf(" --------------- START OF OUTPUT FOR %s ----------------- ", defaultFilenames[i]);

room = read2DArray( defaultFilenames[i] );

printf("Base room: ");

print2DArray( room );

paintRoom( room );

printf(" Room after algorithm: ");

print2DArray( room );

free2DArray( room );

printf(" --------------- END OF OUTPUT FOR %s ----------------- ", defaultFilenames[i]);

}

}

return 0;

}

//Read in and return room from given file

RoomData read2DArray( const char* name )

{

int i, j;

FILE *f = fopen( name, "r" );

char buffer[100];

char* line;

RoomData room;

if( f==NULL || fgets(buffer, 100, f)==NULL || sscanf( buffer, "%d%d", &room.numrows, &room.numcols )!=2 )

{

printf("ERROR - Invalid file format %s ", name);

exit(-1);

}

line = (char*)malloc( sizeof(char)*(room.numcols+10) );

room.roomArray = (char**)malloc( sizeof(char*)*(room.numrows) );

for( i=0; i

{

room.roomArray[i] = (char*)malloc( sizeof(char)*(room.numcols) );

if( fgets( line, room.numcols+10, f ) == NULL )

{

printf("ERROR - Failed to read %dth row ", i+1);

exit(-1);

}

for( j=0; j

room.roomArray[i][j] = line[j];

}

free(line);

/* close file and return created trafficData */

fclose( f );

return room;

}

//Print given 2D array

void print2DArray( RoomData room )

{

int i, j;

for( i=0; i

{

for( j=0; j

printf("%c", room.roomArray[i][j]);

printf(" ");

}

}

//Free given 2D array

void free2DArray( RoomData room )

{

int i;

for( i=0; i

free(room.roomArray[i]);

free(room.roomArray);

}

makefile

# Makefile comments

PROGRAMS = driver

CC = gcc

CFLAGS = -Wall -g

all: $(PROGRAMS)

clean:

rm -f *.o

# C compilations

paintRoom.o: paintRoom.c paintRoom.h

$(CC) $(CFLAGS) -c paintRoom.c

driver.o: driver.c paintRoom.h

$(CC) $(CFLAGS) -c driver.c

# Executable programs

driver: driver.o paintRoom.o

$(CC) $(CFLAGS) -o driver driver.o paintRoom.o

paintRoom.c

#include "paintRoom.h"

void recPaintRoom( RoomData room, int row, int col, int distanceFromA /* feel free to remove/add any other parameters here*/ );

/* declare any other helper functions here*/

/* printName

* input: none

* output: none

*

* Prints name the student who worked on this solution

*/

void printName( )

{

/* TODO : Fill in your name*/

printf(" This solution was completed by: ");

printf(" ");

}

/* TODO

* paintRoom

* input: the room to process

* output: N/A

*

* This non-recursive function is called by the driver and it makes the initial call to recursive function recPaintRoom.

*/

void paintRoom( RoomData room )

{

/* Call any other helper functions (a helper function to find the location of 'A' in room may be handy) */

/* Call your recursive function here */

//recPaintRoom( room, /* initial row value */, /* initial col value */, /* initial value for distanceFromA */ );

}

/* TODO

* recPaintRoom

* input: the room to process, the row and column of the current location being explored, the distance traveled from 'A'

* output: N/A

*/

void recPaintRoom( RoomData room, int row, int col, int distanceFromA /* feel free to remove/add any other parameters here*/ )

{

/* Base cases: */

/* Recursive cases: */

}

paintRoom.h

#ifndef _paintRoom_h

#define _paintRoom_h

#include

#include

/* DO NOT MODIFY THIS FILE */

typedef struct RoomData

{

char **roomArray; /* the 2d char array representing the room shared by Jethro and Cletus */

int numrows; /* the number of rows for the char** roomArray */

int numcols; /* the number of columns for the char** roomArray */

} RoomData;

void printName( );

void paintRoom( RoomData room );

#endif

Jethro and Cletus are quarantined at home and bored. They spend most of their day sitting at their computer monitor working or browsing the internet in their small apartment. Out of boredom Jethro begins counting the number of steps needed to reach each location in their small apartment. After seeing that taking different paths from their computer to their coffee maker yields different numbers of steps a question dawns on them. They want to know what is the fewest number of steps needed to reach all of the locations in their small apartment starting from their computer. Fortunately, Jethro is quite skilled at ASCII art. So they model their room with ASCII characters. A space " 'can be moved through. An asterisk '*' is a wall or furniture that cannot be traversed (no climbing over furniture!). Going up, down, left, right one space takes exactly one step (we'll assume no diagonal movements for that sake of simplicity). For example, here is a possible model of their room: Assume that (0,0) is the upper lefthand corner. For the sake of simplicity you can assume the apartment is enclosed in '*' characters and that the location of Jethro's computer has been marked with an 'A'. Jethro is still new to programming and wants to hire you to write the program to label all of the " 'locations in their apartment with the minimum number of steps needed to reach them. To keep with the ASCII art theme you'll use the letters A-Z Such that: 'A' is 0 stepa 'B' is 1 step 'C' is 2 stepa 'y' is 24 stepa ' Z ' is 25 (or nore) stepa Example 4: Base room: Room after algorithm: AABCDEEFFGGHKJIHI Part 1 - Programming: (15 points) Write a brute force recursive program to solve the problem described above in paint Room.c. Hint 1: This program will take fewer lines of code than previous one but you'll need to think about and test them carefully. For reference, my recPaintRoom only had 10 lines of code in it. Hint 2: From any given space, you need to try to continue moving up, down, left, and right (i.e. 4 recursive calls). return from that call. Hint 4: It may help to track the distance traveled so far from the starting 'A' character. Hint 5: Only updating locations that contain a : won't be enough. Sometimes you'll need to update a location you previously visited and labeled. Hint 6: chars can be treated like small valued integers. In particular, it may be helpful to use operations like ' + ' and '