CS2124 Data Structures Assignment 3 - Recursion Program

Part 1 - Programming: (15 points) Write a brute force recursive program to solve the problem described above in paintRoom.c.

Hint 1: This program will take fewer lines of code than previous one but youll need to think about and test them carefully. For reference, my recP aintRoom 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).

Hint 3: Your algorithm can move into a *, but upon recognizing it as an obstacle, it should 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 wont be enough. Sometimes youll 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

Part 2 - Runtime: (5 points) What is the runtime complexity of your algorithm? There are multiple reasonable answers and the answer depends on your code so you should also justify your reasoning in order to receive credit. Deliverables: Your program solution should be submitted as paintRoom.c (also submit any additional files you created to solve this problem). Your solutions to part 2 should be submitted as a text file (.txt, .pdf, or .doc). Upload these files to Blackboard under Assignment 3. Do not zip your files. To receive full credit, your code must compile and execute. You should use valgrind to ensure that you do not have any memory leaks.

Sample output

MobaTextEditor File Edit Search View Format Encoding Syntax Special Tools 1 paintRoom.c x "include "paintRoom. h " 2 / 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 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: */ SampleOutput (1).txt \begin{tabular}{l|l} 48 & 1.1 \\ 49 & \\ 50 & Base room: \\ 51 \end{tabular} START OF OUTPUT FOR room-Mediume1.txt 61 Room after algorithm: 65BABCDEFGHIJK 66CBCDFGHIJKL * 67DCDEGHIJKLM 68EDHIJKLMN 69FEFGHIJKLMNO 70GFGHIOP 71 HGHIJ***RQPQ* 72 END OF OUTPUT FOR room-Mediume1.txt START OF OUTPUT FOR room-Mediume2.txt Base room: 95 96 *************** 98DEK 99EIHGFL 100FJM 101GKMNPON 102HIJKLMQ 103INR 104JRQPOS 1055T 106 TUVWXWVU* * - END OF OUTPUT FOR room-Mediume2.txt START OF OUTPUT FOR room-Long01.txt Base room: Room after algorithm: *DCBABCDEFGHIJKLMNOPQRSTUVWXYZZZZ* END OF OUTPUT FOR room-Long01.txt START OF OUTPUT FOR room-Longe2.txt Base room: 20 1.. END OF OUTPUT FOR room-Long02........ W.-.-. START OF OUTPUT FOR room-Largee1.txt Base room: Room after algorithm: DCFJKLTUTZZZZZZZZZZZZZZZZZ CBEIMSSZZ 8 *BABCD*H*N*R*RSTUVWXYZZZZZZZZZZZZ* 9CBEFGOPQQZ **EDEFGHIJKLMNOPQR*VWX*ZZZ*ZZZ*ZZZ* 192 FFE**H**************W***************** 193 *GF**I* XYZZZZZZZZZZZZZ 194 *HGHIJ***************** 196 *JI**L*************Y**************** 197 *KJKLM* ZZZZZZZZZZZZZZZ 199 END OF OUTPUT FOR room-Large01.txt START OF OUTPUT FOR room-Large02.txt Base room: * 212 * 19