Using Queues in C++

1make2dArray.cpp

// test the function make2dArray

#include #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

2)make2dArray.h

// create a 2D array; catch exception thrown by new when // sufficient memory is not available // return true iff successful in creating the 2d array

#ifndef make2dArray_ #define make2dArray_

#include

using namespace std;

template bool make2dArray(T ** &x, int numberOfRows, int numberOfColumns) {// Create a two dimensional array.

try { // create pointers for the rows x = new T * [numberOfRows]; // get memory for each row for (int i = 0; i

#endif

3)make2dArray.output

1 2 1 4

4)maze.cpp

// find a path in a maze

#include #include "arrayStack.h" #include "position.h" #include "make2dArray.h"

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

void welcome() {};

void inputMaze() {// Input the maze. cout > size; make2dArray(maze, size + 2, size + 2); cout > 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;

// 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

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

// was a neighbor found? if (option 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 empty()) { here = path->top(); path->pop(); cout

void main() { welcome(); inputMaze(); if (findPath()) outputPath(); else cout

5)maze.input.txt

10 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0

6)position.h

#ifndef position_ #define position_

struct position { int row, // row number of position col; // column number of position

operator int() const {return row;} };

#endif

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