Scribd
Upload
376 views9 pages

Rat in A Maze

This project report describes using a stack data structure to solve the problem of finding a path for a rat to navigate through a maze from an entry point to an exit point without dying by encountering blocked boxes. The report provides the problem statement, algorithm used which involves pushing coordinates to a stack and popping from the stack to backtrack, and output/limitations sections.

Uploaded by

sh laskar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
376 views9 pages

Rat in A Maze

This project report describes using a stack data structure to solve the problem of finding a path for a rat to navigate through a maze from an entry point to an exit point without dying by encountering blocked boxes. The report provides the problem statement, algorithm used which involves pushing coordinates to a stack and popping from the stack to backtrack, and output/limitations sections.

Uploaded by

sh laskar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 9

Project Report

Course Code : CSE207

Course Title : Data Structures

Section : 2

Submitted to

Dr. Maheen Islam.

Assistant Professor, Department of CSE.

Submitted by

Saddam Hossain Laskar

ID : 2017-3-60-072
Nabid Hossain

ID: 2017-3-60-059

Department of Computer Science and Engineering

Date of Submission : 17-4-2019


Introduction:

Rat in a maze is a popular backtracking problem. We have solved this problem


using two data structures, Array and Stack.
Stack: A stack is linear list in which all additions and deletions are restricted to
one end, called top. Stack is known as LIFO - Last in First out.
Two basic operation of stack:
Push – Inserting data into the stack, that is inserting element at the start of the
stack.
Pop – Removing data from the stack that is removing the first element of the
stack.

Problem Statement:
Consider a rat in a maze. There is a selected entry and a selected exit point.
The maze has two type of boxes, one of them is blocked and using another the
rat can go through. If the rat goes in a blocked block that means the rat would
be dead. So, the rat will have to avoid blocks (Death). The rat will have to find a
path using which it can reach the destination from the source without dying. Find
a path from the entry to the exit that won’t make the rat dead.
Algorithm:
❑Choose a source & destination point.

❑If the point is valid continue.

❑Else input source & destination point until a valid point is found.

❑If the chosen point is valid,

❑Then move in the following sequence,

Left
Right
Down
Up

❑If the value at the position is zero and there several paths, that means it’s
a decision point.

The mouse can choose either way.


The mouse will traverse the way, if the way cannot lead to destination it
will return to the decision point.
Push the co-ordinates into stack.

❑If a direction cannot lead to the destination point pop until decision
point is found.
❑Now check other direction from the diction point.
❑If the rat can reach the destination point print “The mouse has exited
the maze”.
❑Else print “The mouse is trapped”.
❑If users want repeat from the first step.
Output:
Limitations:

1. Time complexity (We could reduce the time it consumes to execute).

2. Here we only showed the 2D maze matrix. But we can further


develop it by adding mouse movement and show the path through the
maze moved by the mouse. For that we need graphics concepts.

3. Maze size here is not adjustable.

You might also like