The problem is like this:-
A maze is a rectangular area, with m rows and n columns, with an entrance and an exit. The interior of the maze contains obstacles. The entrance is at the upper-left corner, and exit is at the lower-right corner. A rat in a maze problem is to find a path from the entrance to exit of a maze. A path is basically a sequence of positions, none of which is blocked, and such that each (east,west south,north) neighbour of the preceding position. Write a program to find such path, if exits, otherwise output the message "No solution for this maze"
2 3827 D_C 293
Contributor
A recursive solution is the way to do it. Suppose you have a data structure maze, which contains the current (x,y) position of the rat, and also an mxn matrix with obstacles and the rat's "history" marked (which locations it has visited). Your algorithm should be something like: - if(rat is in the exit position)
-
{
-
do what is necessary;
-
return;
-
}
-
if(rat has not been left) // go left
-
{
-
move left;
-
solve maze;
-
move right; // undo going left
-
}
-
// similarly for go down, go right, and go up also
The problem is like this:-
A maze is a rectangular area, with m rows and n columns, with an entrance and an exit. The interior of the maze contains obstacles. The entrance is at the upper-left corner, and exit is at the lower-right corner. A rat in a maze problem is to find a path from the entrance to exit of a maze. A path is basically a sequence of positions, none of which is blocked, and such that each (east,west south,north) neighbour of the preceding position. Write a program to find such path, if exits, otherwise output the message "No solution for this maze"
CODE:
1.start at entrance.
2.at this point u may have 3 ways to move forward,select any one of that ,say(i,j)th cell.
3.mark it as visited.
4.simultaneousl y build a tree using the marked cells along with entrance &exit.
5.so at this point u may have again 3 ways ,choose any one
if this is an obstacle,mark as deadend &backtrace
else repeat steps 2,3,4,5until u reach exit.
Sign in to post your reply or Sign up for a free account.
Similar topics |
by: Naren |
last post by:
Hello All,
I dont get errors but I get warnings though the code runs fine.
Could anyone help me removing these warnings
c:\program files\microsoft visual studio\vc98\include\vector(48) : warning
C4786:
'??0?$vector@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@V...
|
by: jacob navia |
last post by:
In C, we have read-only memory (const), read/write memory
(normal data), and write only memory.
Let's look at the third one in more detail.
Write only memory is a piece of RAM that can only
be written to, since its contents are undefined.
The program is allocating a new piece of data, and
the previous contents aren't relevant. This...
|
by: roopeman |
last post by:
i wrote the below code , just want got local machine application Eventlog 's
message , and write to MDB.but it 's can not write the message to Mdb,
somebody can check it for me? thanks!
//-----------------------------------------------------------------------
//Wrote by Michael April 30 2005...
|
by: Chris |
last post by:
Hi,
I am working on a small which involves a touchscreen and I need to create a
on-screen keyboard. I need some assistance with a few questions
1. For the the buttons, do I user their text as the value, that is, when the
user presses e.g "A" do I use the button text as the value to work with or
Key.ASCII?
2. While the user is pressing...
|
by: Siddhu |
last post by:
Hai, i am student & i have struck up with the following program's
output. Kindly help me to reason out why the output goes as which is
given below.
THE PROGRAM goes as;
#include<iostream.h>
#include<conio.h>
void main()
{ int i=0,x={1,2,3,4,5},y={5,4,3,2,1},r={0,0,0,0,0};
while(i++<5)
| |
by: nikki123 |
last post by:
Hi all,
can anyone help me for the following C++ program.
i want to write a program which read a file of C language and Print Lines of Codes and print signature of all function (including main) in that file.
please give me code for this program or tell me the logic to develop this program.
|
by: Sachin Garg |
last post by:
I have a program which opens a fstream in binary input+output mode, creating
the file if it doesn't exists. But writing doesn't works after reading, it
must be something obvious that I am not aware of.
f.open(filename,ios::in | ios::out | ios::binary | ios::trunc)
The program flow is
1) write some data
2) read the data
|
by: vijayrvs |
last post by:
SearchCrawler.java
The program search crawler used to search the files from the website.
From the following program i got 7 compiler error. can any body clarify it and provide me solution.
import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.net.*;
import java.util.*;
|
by: sreekandank |
last post by:
I want to implement POP3 program in java....I have written the code like...
import javax.mail.*;
import javax.mail.internet.*;
import java.util.*;
import java.io.*;
public class POP3Client {
public static void main(String args) {
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
| |
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in...
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating...
| |