Using Queues in C++, for Rat in Maze and Wire Router. (2 parts) 1)make2darray.cp

Question

Using Queues in C++, for Rat in Maze and Wire Router. (2 parts)

1)make2darray.cpp

// test the function make2dArray

#include <iostream>
#include "make2dArray.h"

using namespace std;

int main()
{
int **a;
// make a 2 x 2 array
make2dArray(a,2,2);

// assign values to all elements of the array
a[0][0] = 1; a[0][1] = 2; a[1][0] = 3; a[1][1] = 4;

// output assigned values
cout << a[0][0] << ' ' << a[0][1] << endl;
cout << a[0][0] << ' ' << a[1][1] << endl;
return 0;
}

2)

// find a path in a maze

#include <iostream>
#include "arrayStack.h"
#include "position.h"
#include "make2dArray.h"

// globals
int **maze, size;
arrayStack<position>* path; // pointer to stack

void welcome() {};

void inputMaze()
{// Input the maze.
cout << "Enter maze size" << endl;
cin >> size;
make2dArray(maze, size + 2, size + 2);
cout << "Enter maze in row major order" << endl;
for (int i = 1; i <= size; i++)
for (int j = 1; j <= size; j++)
cin >> maze[i][j];
}

bool findPath()
{// Find a path from (1,1) to the exit (size, size).
// Return true if successful, false if impossible.

path = new arrayStack<position>;

// initialize offsets
position offset[4];
offset[0].row = 0; offset[0].col = 1; // right
offset[1].row = 1; offset[1].col = 0; // down
offset[2].row = 0; offset[2].col = -1; // left
offset[3].row = -1; offset[3].col = 0; // up

// initialize wall of obstacles around maze
for (int i = 0; i <= size + 1; i++)
{
maze[0][i] = maze[size + 1][i] = 1; // bottom and top
maze[i][0] = maze[i][size + 1] = 1; // left and right
}

position here;
here.row = 1;
here.col = 1;
maze[1][1] = 1; // prevent return to entrance
int option = 0; // next move
int lastOption = 3;

// search for a path
while (here.row != size || here.col != size)
{// not exit
// find a neighbor to move to
int r, c;
while (option <= lastOption)
{
r = here.row + offset[option].row;
c = here.col + offset[option].col;
if (maze[r][c] == 0) break;
option++; // next option
}

// was a neighbor found?
if (option <= lastOption)
{// move to maze[r][c]
path->push(here);
here.row = r;
here.col = c;
maze[r][c] = 1; // set to 1 to prevent revisit
option = 0;
}
else
{// no neighbor to move to, back up
if (path->empty())
return false; // no place to back up to
position next = path->top();
path->pop();
if (next.row == here.row)
option = 2 + next.col - here.col;
else option = 3 + next.row - here.row;
here = next;
}
}

return true; // at exit
}

void outputPath()
{// Output path to exit.
cout << "The path is" << endl;
position here;
while (!path->empty())
{
here = path->top();
path->pop();
cout << here.row << ' ' << here.col << endl;
}
}

void main()
{
welcome();
inputMaze();
if (findPath())
outputPath();
else
cout << "No path" << endl;
}

Rat in Maze (5 points) o Consider the “Rat in Maze" application that was discussed in class. The given “Rat in Maze code.zip" includes: ” C++ code that implements this application ” C++ code that implements the Stack Abstract Data Type (ADT) using ArrayStack - Sample input grid 1. Reproduce this application in your work environment and submit the output corresponding to the given input. 2. Assume that we have a 10x10 Maze (i.e. 10 rows by 10 columns, excluding the additional surrounding walls). Draw a diagram of this 10x10 grid that shows a worst case scenario in which the ArrayStack has to grow to a maximum. I.e. a scenario in which the grid configuration results in a longest possible sequence of push operations before any pop operation occurs. 3. Now assume that we have an N by N Maze. Give a simple formula in terms of N depicting the maximum number of elements that might have to be pushed on the ArrayStack used to solve the "Rat in Maze" problem. Your formula doesn't have to be exact, just a good approximation. For example, N2 or (N2 /2) or (N2 -N) or (N2-4N), etc … Image Component Labeling Slide # 2

Explanation / Answer

1) The required header files are missing : make2dArray.h, arrayStack.h,position.h

2) The worst case scenario will occur when there is a cycle in the maze that is when the rat moves through a sequence oof cells to find itself back at the start node and has to start all over again.

3) The algorithm used here is a traversal of 2 dimensional array(matrix) . At every step there are at most 3 move options [0..2]. So the computaional complexity in this case is O(constant * n^2)

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.