Maze Backtracking

I don't know what's wrong with this code

Page 1 of 1

5 Replies - 10242 Views - Last Post: 03 May 2008 - 08:04 AM Rate Topic: -----

#1 Hector6008   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 25
  • Joined: 14-October 07

Maze Backtracking

Posted 01 May 2008 - 12:10 PM

Would you please tell me what's wrong with this code??
Thanks a lot.

#include<iostream>
#define num 4
using namespace std;
class cnode
{
public:
	char x[num][num];
	cnode *pnext;
	int sr,sc,er,ec;
};
class cstack
{
public:
	cnode *h,*t;
	cstack()
	{
		h=t=NULL;
	}
	~cstack()
	{
		cnode*ptrav=h;;
		while(h!=NULL)
		{
			h=h->pnext;
			delete ptrav;
			ptrav=h;
		}
	}
	void push(cnode *pnn)
	{
		pnn->pnext=h;
		h=pnn;
	}
	cnode *pop()
	{
		if(h==NULL)
			return NULL;
		else
		{
			cnode *ptrav=h;
			h=h->pnext;
			ptrav->pnext=NULL;
			return ptrav;
		}
	}

};

void Display(cnode *pnn)
	{
		for(int r=0;r<num;r++)
		{
			for(int c=0;c<num;c++)
			{
				cout<<pnn->x[r][c]<<" ";
			}
			cout<<endl;
		}
	}

void DoCopy(cnode*pcurr,cnode*pnn)
{
	for(int i=0;i<num;i++)
	{
		for(int j=0;j<num;j++)
		{
			pnn->x[i][j]=pcurr->x[i][j];
		}
	}
	pnn->sr=pcurr->sr;
	pnn->sc=pcurr->sc;
	pnn->er=pcurr->er;
	pnn->ec=pcurr->ec;
	pnn->pnext=NULL;
}
cnode* DoIntialize()	 
{
	cnode*pnn=new cnode();
	cout<<"Create your Maze \n";
	for(int R=0;R<num;R++)
	{
		for(int C=0;C=num;C++)
		{
			cin>>pnn->x[R][C];
			Display(pnn);
			if(pnn->x[R][C]=='^')
			{
				pnn->sr=R;
				pnn->sc=C;
			}
			if(pnn->x[R][C]=='@')
			{
				pnn->er=R;
				pnn->ec=C;
			}
		}
	}
	pnn->pnext=NULL;
	return pnn;
}

int IsSolution(cnode *pcurr)
{
	if((pcurr->sr==pcurr->er)&&(pcurr->sc==pcurr->ec))
		return 1;
	else
		return 0;
}
void DoExpand(cnode *pcurr,cstack &s)
{
	cnode*pnn;
	if((pcurr->sr<num)&&(pcurr->x[pnn->sr+1][pnn->sc]=='-'))
	{
		pnn=new cnode();
		DoCopy(pcurr,pnn);
		pnn->x[pnn->sr][pnn->sc]='*';
		pnn->sr--;
		pnn->x[pnn->sr][pnn->sc]='^';
		s.push(pnn);
	}
	if((pcurr->sr<num)&&(pcurr->x[pnn->sr+1][pnn->sc]=='-'))
	{
		pnn=new cnode();
		DoCopy(pcurr,pnn);
		pnn->x[pnn->sr][pnn->sc]='*';
		pnn->sr++;
		pnn->x[pnn->sr][pnn->sc]='^';
		s.push(pnn);
	}
	if((pcurr->sc>0)&&(pcurr->x[pnn->sr][pnn->sc-1]=='-'))
	{
		pnn=new cnode();
		DoCopy(pcurr,pnn);
		pnn->x[pnn->sr][pnn->sc]='*';
		pnn->sc--;
		pnn->x[pnn->sr][pnn->sc]='^';
		s.push(pnn);
	}
	if((pcurr->sc<num)&&(pcurr->x[pnn->sr][pnn->sc+1]=='-'))
	{
		pnn=new cnode();
		DoCopy(pcurr,pnn);
		pnn->x[pnn->sr][pnn->sc]='*';
		pnn->sc++;
		pnn->x[pnn->sr][pnn->sc]='^';
		s.push(pnn);
	}
}
void DoBackTrack()
{
	cstack s;
	cnode*pcurr;
	pcurr=DoIntialize();
	s.push(pcurr);
	while(s.h!=NULL)
	{
		pcurr=s.pop();
		if(IsSolution(pcurr))
		{
			cout<<"Possible solution\n";
			Display(pcurr);
		}
		DoExpand(pcurr,s);
	}
}


void main()
{
	 DoBackTrack();
}






This post has been edited by Hector6008: 01 May 2008 - 12:12 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Maze Backtracking

#2 gabehabe   User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1433
  • View blog
  • Posts: 11,006
  • Joined: 06-February 08

Re: Maze Backtracking

Posted 01 May 2008 - 12:21 PM

The only problem I can see is that main should return an int. Is there something that it should do but doesn't?
Was This Post Helpful? 0
  • +
  • -

#3 Hector6008   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 25
  • Joined: 14-October 07

Re: Maze Backtracking

Posted 01 May 2008 - 12:31 PM

View Postgabehabe, on 1 May, 2008 - 12:21 PM, said:

The only problem I can see is that main should return an int. Is there something that it should do but doesn't?


The display function doesn't display the whole matrix, it only displays a single character.
Was This Post Helpful? 0
  • +
  • -

#4 gabehabe   User is offline

  • GabehabeSwamp
  • member icon




Reputation: 1433
  • View blog
  • Posts: 11,006
  • Joined: 06-February 08

Re: Maze Backtracking

Posted 01 May 2008 - 01:08 PM

So what should output look like? Can you give me an example? It displays it all for me, I'm not sure if it displays properly though.
Was This Post Helpful? 0
  • +
  • -

#5 Hector6008   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 25
  • Joined: 14-October 07

Re: Maze Backtracking

Posted 01 May 2008 - 02:43 PM

View Postgabehabe, on 1 May, 2008 - 01:08 PM, said:

So what should output look like? Can you give me an example? It displays it all for me, I'm not sure if it displays properly though.

Ex:
# = obstacle
^ = Start cell
@ = Finish cell
- = empty cell
% =garbage value

in the first time if i entered # the display should be:

# % % %
% % % %
% % % %
% % % %
the second time i entered - the display should be:

# - % %
% % % %
% % % %
% % % %
and so on till i fill the whole matrix

# - @ -
- - - #
# - - #
# ^ - #

Thanks a lot.
Was This Post Helpful? 0
  • +
  • -

#6 Hector6008   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 25
  • Joined: 14-October 07

Re: Maze Backtracking

Posted 03 May 2008 - 08:04 AM

would you please tell me what's wrong with my code???? :angry: :angry:
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1