Member Avatar for Dimitar

I have an input file which is a 4X4 matrix, and each item of the matrix is represented by 4 digits 0's and 1's. 1 is closed and 0 means open, the direction is NSEW ( first digit represents North and so on..). I'm trying to recursively find my way from 1 point to another in the maze. Please help :)

Also I am using a stack to store my data, i have coded that up in a .h file along with an overloaded extraction operator so I can do stuff like fout<< Path.Push(data);

#include <iostream>
#include "Maze.h"
#include <fstream>
# include <iomanip>
# include "string"

using namespace std;

//NSEW
//0123

string walkThrough(int startX, int startY, int endX, int endY, int dim1, int dim2, string A[][10])
{
	maze<string> Path;
	ofstream fout("output1.txt");

	Path.Push(A[startX][startY]);
	fout << " Start: " <<Path.peekTop()<<endl;
	
	if(A[startX-1][startY][0]==1)
				{
					fout << "ye it "<<endl;
	}
	bool visitedN=true;
	bool visitedS=true;
	bool visitedE=true;
	bool visitedW=true;
	
	//check North
	if(visitedN==true)
	{
		if((startX>0 ||startX==0)&& (startY>0||startY==0))
		{
			if(startX-1!=-1)
			{
				if(A[startX-1][startY][0]==0)
				{
					Path.Push(A[startX-1][startY]);
					
					fout << " North: "<<Path.peekTop()<< endl;

					if(startX-1!=endX && startY!=endY)
					{
						visitedS=false;
						return walkThrough(startX-1, startY, endX, endY, dim1, dim2, A);
					}
					else
						return 0;
				}
				else

					visitedN=false;
			}
			else
				Path.Pop();
			visitedN=false;
		}
		else
			Path.Pop();
		visitedN=false;
	}
	else
		//check South
		if(visitedS==true)
		{
			if((startX>0 ||startX==0)&& (startY>0||startY==0))
			{
				if(startX+1<dim1 ||startX+1==dim1)
				{
					if(A[startX+1][startY][1]==0)
					{
						Path.Push(A[startX][startY]);

						fout <<  " South: "<<Path.peekTop()<<endl;
						if(startX+1!=endX && startY!=endY)
						{
							visitedN=false;
							return walkThrough(startX+1, startY, endX, endY, dim1, dim2, A);
						}
						else
							return 0;
					}
					else

						visitedS=false;
				}
				else
					Path.Pop();
				visitedS=false;
			}
			else
				Path.Pop();
			visitedS=false;
		}
		else
			//check West
			if(visitedW==true)
			{
				if((startX>0 ||startX==0)&& (startY>0||startY==0))
				{
					if(startY-1!=-1)
					{
						if(A[startX][startY-1][2]==0)
						{
							Path.Push(A[startX][startY]);

							fout <<  " West: "<<Path.peekTop()<<endl;
							if(startX!=endX && startY-1!=endY)
							{
								visitedE=false;
								return walkThrough(startX, startY-1, endX, endY, dim1, dim2, A);
							}
							else
								return 0;
						}
						else

							visitedW=false;
					}
					else
						Path.Pop();
					visitedW=false;
				}
				else
					Path.Pop();
				visitedW=false;
			}
			else
				//check East
				if(visitedE==true)
				{
					if((startX>0 ||startX==0)&& (startY>0||startY==0))
					{
						if(startY+1<dim2 ||startY+1==dim2)
						{
							if(A[startX][startY+1][3]==0)
							{
								Path.Push(A[startX][startY]);
								
								fout <<  " East: "<<Path.peekTop()<<endl;
								if(startX!=endX && startY+1!=endY)
								{
									visitedW=false;
									return walkThrough(startX, startY+1, endX, endY, dim1, dim2, A);
								}
								else
									return 0;
							}
							else

								visitedE=false;
						}
						else
							Path.Pop();
						visitedE=false;
					}
					else
						Path.Pop();
					visitedE=false;
				}

	fout.close();
}

int main()
{


	ifstream fin("input1.txt");
	ofstream fout("output1.txt");

	int start1, start2, end1, end2, dimenssion1, dimenssion2;
	
	string matrix[10][10];



	if(fin.fail())
	{
		cerr << "Unable to open input1.txt!\n";
		exit(2);
	}
	fin >> start1 >> start2 >> end1 >> end2 >> dimenssion1 >> dimenssion2;


	for(int k=0; k<dimenssion1; k++)
	{
		for(int g=0; g<dimenssion2; g++)
		{
			fin >> matrix[k][g];
		}

	}


	//check if there is at least 1 possible way to go
	//from the starting point
	if(matrix[start1][start2]=="1111")
	{
		cerr << " There is no solution to the problem\n";
		exit(2);
	}
	//checking if the start and the solution are at the same cell
	if(start1==end1 && start2==end2)
	{
		fout << matrix[start1][start2]<<endl;
	}

	walkThrough(start1, start2, end1, end2, dimenssion1, dimenssion2, matrix);



	fin.close();
	fout.close();
	return 0;
}
  • 3 Contributors
  • 2 Replies
  • 72 Views
  • 8 Hours Discussion Span
  • Latest Post Latest Post by zentropy
Member Avatar for NathanOliver

Just turn right.

Member Avatar for zentropy

Below is the general outline of how you would use backtracking / branch and bound to solve it.

bool promising( node n); // returns true if n is solution or could lead to solution
void checknode( node n)
{
  if( promising(n))
  {
    if(node is target point)
    {
      writeSolution();
    }

    else
    {
      for each node m that is adjacent to n
      {
         checknode(m)
      }
    }

  }

}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.