jl_7

I have this for homework for tomorrow and I can't do it.
Please if there is anyone that can help.

Find a way in a maze

Write a program that finds way between two points in certain maze.
The maze is rectangular matrix which consists of cells. Each cell is from one of the following 4 types and it can be represented with one positive number.
1. Void (blank space) – This cell is empty and you can go through it. Represented by 0 (zero).
2. Wall – in this cell there is a wall and you can’t go through it. Represented by 100.
3. Key – this cell contains a key with a given number. You can go through it, and when you do that a “door” with corresponding number to the key opens. Represented by the numbers from 1 to 20. Key number 1, 2, ………20.
4. Door – this cell is a wall. You can walk through it only if you walked on key which is corresponding to this wall. Represented by the numbers from 101 to 120, respectively for wall number 101, 102, 103, ……….120.
In the maze there can not be more than 20 walls, and 20 keys.

Information for the maze can be written in text file according to this format:
On the first line there are 2 positive integer numbers N(3 < N < 10)- the width of the maze and M(3 < M < 10)- length of the maze. Followed by 4 numbers
SX (0 < SX < N) , SY (0 < SY < M) , TX (0 < TX < N) , TY (0 < TY < M),
which are the start position (SX, SY) and the final position (TX, TY) in the maze. These are the two positions between you have to find a way.
Then there is M in number of lines with N in numbers of numbers on each line. They describe the contents of each cell of the maze as it is described in 1(void), 2(wall), 3(key), 4(door).


And thank you for your help.

jl_7

I almost have a solution but there are some places that it is witten what exactly to do to complate the program but I can not do it so it you can please help.

bool LabPath( int [][] maze, int[][] Path, int xpos, int ypos )
{
int [][] TempMaze = maze[][];
int [][] TempPath = Path[][];

if ( xpos == xend and ypos == yend )
{
You add maze[xpos][ypos] to TempPath[][]
solution[][] = TempPath[][];
return true;
}

if ( TempMaze[xpos][ypos] >= 100 and TempMaze[xpos][ypos] <= 120 )
return False;

if ( TempMaze [xpos][ypos] >= 1 and TempMaze[xpos][ypos] <= 20 )
{
in TempMaze[][] you find the cell with value = ( TempMaze [xpos][ypos] +100 ) and you give it a value = 0
the door is open
for( i ... )
for( j ... )
if ( TempMaze [i][j] == ( TempMaze [xpos][ypos] +100 ))
TempMaze [i][j] = 0;

}
// the visited cells in the maze we mark with 40
if ( TempMaze [xpos][ypos] == 40 )
return False;
else
{
TempMaze[xpos][ypos] = 40;
add [xpoa, ypos] to TempPath[][];
return LabPath( TempMaze, TempPath, xpos + 1, ypos ) or
LabPath( TempMaze, TempPath, xpos - 1, ypos ) or
LabPath( TempMaze, TempPath, xpos, ypos +1 ) or
LabPath( TempMaze, TempPath, xpos, ypos - 1 )


}

}

// global variables
int lab[][];
int lab1[][];
int path1[][] =[];
int solution[][] = [];
int xbegin, xend, ybegin, yend;

main( argc, argv )
{

Open fail in.txt for reading
lab[M][N] = data for the maze
xbegin, ybegin = start position
xend, yend = end position

you create lab1[M+2][N+2] array and you copy the whole lab[m][n] in it from position (1, 1) to (M,N), and the points on the walls of the new array lab1[][] you mark them as walls. They are = 100(you surround the array with wall, it is needed so that the function can work)

LabPath( lab1, path1, xbegin, ybegin );

if ( solution[][] = [] )
Nosolution
else
{
You open out.txt

Write down the found way from solution[][], and this solution is for lab1 array, it is with bigger size then the needed array so, you must take out 1 from the coordinates of the found solution on the axis X and Y
}

}

nnxion

Read the "How to post a question" thread at the top of the forum, and edit your posts accordingly.

__________________
"Employ your time in improving yourself by other men's writings, so that you shall gain easily what others have labored hard for."
-- Socrates

DaWei

But hey, I thought rude, thoughtless, and selfish was the 'in' thang....

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers