You cannot submit for this problem because the homework's deadline is due.

Ex3. Treasure in the maze (15 marks)

This exercise aims to get you familiar with file i/o and also serves as an exercise for recursion.

A hamster happen to find a maze with treasure inside! To help it get the treasures, you are going to use Depth-First Search (DFS) algorithm to search all accessible locations inside the maze.

The map is written in a simple text file composed of a first line showing the size of the maze \(x\) and \(y\). The rest of the file contains \(x\) lines each with \(y\) columns. Those remaining lines can only feature four types of characters:

• . to show a path, i.e. can walk there
• X to represent a wall, i.e. the path is blocked
• s to specify the starting point
• t to locate a treasure

Here is a concrete example:

The map of the maze is stored in a file, and the filename would be given in the input. All of your output should be printed in output.txt so that hamster could find it in the first time. i.e.

filename = input('','s'); % the 's' here matters!!!
fin = fopen(filename,'r');
fout = fopen('output.txt','w')
...
% closing the files is really IMPORTANT!!!
fclose(fin); flocse(fout);

Task 1

Your first task is to read from the given file and locate the starting point s. You should print

Start at location row: %d, column: %d

Task 2

Your second task is to search the maze using dfs with priority: down, right, up, left. Once a treasure is found, you should print

Treasure at location row: %d, column: %d

After you have found all the accessible treasures, print out the total number of treasures.

%d Treasure(s) found in all.

Sample testcase

input:

map.txt

inside map.txt (this is slightly different from the picture above :stuck_out_tongue_winking_eye: )

4 5
XX..t
....X
X.X.t
s.X..

output: (in output.txt)

Start at location row: 4, column: 1
Treasure at location row: 3, column: 5
Treasure at location row: 1, column: 5
2 Treasure(s) found in all.

Hints:

For Task 1

1. Recall the file input functions learned in the lecture. e.g. fscanf,fgetl,fgets, which ones are most suitable here?
2. To locate a certain character, you may use strfind. Explore its documentation!

For Task 2

You don't need to know much about the dfs algorithm very much. Just try to fill out the blanks in the codes attached below if you haven't got an idea.

function [map,count] = dfs(map,locX,locY,rowsMax,columnsMax,count,fout) 
    % EFFECTS: Use dfs algorithm to search the treasures in the maze!
    % "map" is a matrix storing the map of the maze
    % "locX", "locY" stand for the current position
    % "rowsMax", "columnsMax" stand for the size of the maze
    % "count" stands for the number of treasures have been found
    % "fout" is just for file output
 
    % A treasure found!
    if map(locX,locY) is treasure
        fprintf(fout,"Treasure at location row: %d, column: %d\n",locX,locY);
        count = count + 1;
    end
    
    % Now, this place is visited, so it should be marked.
    ...; % only one line of code
    
    % Move on ,go to the neighbor spot
    % Priority: down, right, up, left
    dx = ...;
    dy = ...;
    
    for i in all directions
        
        % Calcuate the coordinates
        new_locX = ...;
        new_locY = ...;
        
        % Only if the new spot is still in the maze
        % and it is not visited yet, we do the dfs.
        
        if (is_inside(...) && ...) % think about what parameters should be here!
            % question: could the order of two condition be changed?
            [map,count] = dfs(...);
        end
        
    end

end

function result = is_inside(...)
    % EFFECTS: return (logical)1 if the point (X,Y) is inside the maze
    result = ...;
end