Question

You are required to become familiar with the workings of the Rat in a Maze program and make certain adjustments to the program. To become familiar with the program I suggest that you run it several times, using a different maze and maybe a different food location. Also trace by hand to ensure you understand how each step works. The adjustments to be made are:

1. Allow the RAT to move in a diagonal direction, so now there are a maximum of eight possible moves

2. Write a function to print the path from the start state (initial location of the RAT), to the goal state (location of the food)

Your program should prompt the user for the coordinates of the initial state and of the goal state.

Answer 1

The program is 0 index based. I have used BFS to find the shortest path and printing it

All the eight directions are represted using pairs like (1,0) -> mean can move left

And at the end there is one demo test case to check the program

Program

#include"iostream"
#include"vector"
#include"queue"
#include"stack"
using namespace std;

struct node
{
   int x;
   int y;
   int pre;
};
int m, n;
int head = 0; int tail = 1;
node start, EN;

// Pair showing it can move in 8 directions
int dis[8][2] = { { 1, 1},{ -1, 0 },{ 1, 0 },{1, -1},{-1, 1},{ 0, -1 },{ 0, 1 },{-1, -1} };

// Print and respective output of final results
void print_path(int tail, node* que)
{
    if (que[tail].pre != -1)
        print_path(que[tail].pre, que);
   cout << "{" << que[tail].x << "," << que[tail].y << "}" << "\n";
   return;
}

// Shortest path using BFS
int BFS(vector<vector<int>> maze, node* que)
{
   node point;
   point = start;
   que[head] = point;
   vector<vector<int>> flag(m, vector<int>(n, 0));
   flag[point.x][point.y] = 1;
   while (head<tail)
   {
       for (int i = 0; i<8; i++)
       {
           int tx = que[head].x + dis[i][0];
           int ty = que[head].y + dis[i][1];

           if (tx<m && tx >= 0 && ty<n && ty >= 0 && maze[tx][ty] == 0)
           if (flag[tx][ty] == 0)
           {
               que[tail].x = tx;
               que[tail].y = ty;
               que[tail].pre = head;
               flag[tx][ty] = 1;
               if (tx == EN.x && ty == EN.y)
               {
                   //head is the first step to the end point.
                   return tail;
               }
               tail++;
           }
       }
       head++;
   }
   return 0;
}

int main()
{
        cin>>m>>n;   // Size of maze
        node *que = new node[n*m];
        head = 0; tail = 1;
      
        // Taking start and end as the input
        int sx,sy,ex,ey;
        cin>>sx>>sy>>ex>>ey;
      
        // Assigning the values
       start.x = sx; start.y = sy; start.pre = -1;
       EN.x = ex; EN.y = ey; EN.pre = -1;
      
        // Taking maze as the input where 1 means wall and 0 means empty path
       vector<vector<int>> maze(m, vector<int>(n, 0));
       for (int i = 0; i<m; i++){
           for (int j = 0; j<n; j++)
           {
               cin >> maze[i][j];
           }
       }
      
        // Finding the shortest path
       int tail = BFS(maze, que);
      
        // Printing the path
        print_path(tail, que);
       delete []que;
      
   return 0;
}

Example

5 5    // size
0 0   // start
3 4   // End

0 0 0 0 0  
1 1 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 0 0 0

// Path
{0,0}
{0,1}
{1,2}
{1,3}
{2,4}
{3,4}