Expert: Narendra - 11/20/2004

Question
Hi...
I write this program and I have a bug but I don't now where, I check it 100 times and I don't find it.
Could u help me?!
The program is how to find the exit in the maze using stack and queue.
My problem is when the maze has no exit.

#include <stdio.h>
#include <stdlib.h>

/*============================================================================*/

//                          \\\\\ Stack /////

struct stacknode
{
int x;
int y;
struct stacknode *next;
};

typedef struct stacknode StackNode;
typedef StackNode *Stack;

/*============================================================================*/

//                          \\\\\ Queue /////


struct queueNode
{
int x;
int y;
struct queueNode * next;
};
typedef struct queueNode QueueNode;
typedef QueueNode * QueueNodePtr;

typedef struct
{
QueueNodePtr   front,rear;
int Count;
}Queue;

/*============================================================================*/

//                        \\\\\ Insert in Queue /////

void Enqueue(Queue *q,int i,int j)
{
if((*q).Count==0)
{
 (*q).rear = (QueueNode*)malloc(sizeof(QueueNode));
 (*q).front = (*q).rear;
}
else
{
(*q).rear->next = (QueueNode*)malloc(sizeof(QueueNode));
(*q).rear = (*q).rear->next;
}
(*q).rear->x = i;
(*q).rear->y = j;
(*q).rear->next = NULL;
((*q).Count)++;
return;
}
/*============================================================================*/

//                        \\\\\ Delete Queue /////

void Dequeue(Queue *q)
{
QueueNodePtr f;
f = (*q).front;
(*q).front = (*q).front->next;
free(f);
((*q).Count)--;
}
/*============================================================================*/

//                 \\\\\ Check The Stack if Empty /////

int isEmpty(Stack S)
{
return (S==NULL);
}
/*============================================================================*/

//                        \\\\\ Check The Queue If Empty /////

int isQueueEmpty(Queue q)
{
if(q.Count==0)
 return 0;
else
 return 1;
}
/*============================================================================*/

//                               \\\\\ Push /////

void Push(Stack *S,int i,int j)
{
Stack q;
q = (Stack)malloc(sizeof(StackNode));
q->x = i;
q->y = j;
q->next = (*S);
(*S) = q;
}
/*============================================================================*/

//                               \\\\\ Pop  /////

void Pop(Stack *S)
{
Stack q;
q = (*S);
(*S) = (*S)->next;
free(q);
}
/*============================================================================*/

//                         \\\\\ Print The Stack /////

void PrintStack(Stack S)
{
Stack Q;
Q = S;
printf("\n\n\n");
if(isEmpty(Q))
{
 printf("\n No Path \n");
 return ;
}
else
{
 printf("\n*********************\n");
 printf("*      The Path     *");
 printf("\n*********************\n");
 while(!isEmpty(Q))
 {
  printf("<%d,%d> , ",Q->x,Q->y);
  Pop(&Q);
 }
 printf("\n\n");
}
}
/*============================================================================*/

//                         \\\\\ Print The Queue /////

void PrintQueue(Queue Q)
{
printf("\n\n\n");
if(!isQueueEmpty(Q))
{
 printf("\n END The Steps \n");
 return ;
}
else
{
 printf("\n*********************\n");
 printf("*     The Step      *");
 printf("\n*********************\n");
 while(isQueueEmpty(Q))
 {
  printf("<%d,%d> , ",Q.front->x,Q.front->y);
  Dequeue(&Q);
 }
 printf("\n\n");
}
}
/*============================================================================*/

//                         \\\\\ Initialize The Array /////

void Initialize(int A[][11])
{
int i,j;
for(i=0;i<=11;i++)
 for(j=0;j<=11;j++)
  A[i][j]=8;
return;
}
/*============================================================================*/

//                         \\\\\ Read From File /////

void Read(int A[][11])
{
int i,j;
FILE *fp;
char file[20];
printf("\n Enter the Name of the File \n");
scanf("%s",file);
fp = fopen(file,"r");

if(fp==NULL)
 printf("\n Error With File Maze \n");
else
 for(i=1;i<=10;i++)
  for(j=1;j<=10;j++)
    fscanf(fp,"%d",&A[i][j]);
fclose(fp);
}
/*============================================================================*/

//                         \\\\\ Print The Array /////

void Print(int A[][11])
{
int i,j;
for(i=0;i<=11;i++)
{
 for(j=0;j<=11;j++)
  printf(" %d ",A[i][j]);
 printf("\n\n");
}
return;
}
/*============================================================================*/

//                         \\\\\ Find The Begin /////

void FindTheStart(int A[][11],int *i,int *j,int *Ans)
{
for((*j)=0;(*j)<10;(*j)++)
 for((*i)=0;(*i)<10;(*i)++)
  if(A[*i][*j]==2)
  {
   *Ans=1;
   return;
  }
printf("\n There is No Enter \n");
return ;
}
/*============================================================================*/

//                          \\\\\ Start MaZe /////

void EnterMaze(int A[][11],int *PathCount,int *StepCount)
{
int i,j,Answer=-1;
Stack S;
Queue Q;

S = NULL;
Q.rear = NULL;
Q.front = NULL;
Q.Count = 0;

FindTheStart(A,&i,&j,&Answer);

if(Answer == -1)
 return ;

printf("\n\n The Enter From i=%d j=%d \n\n",i,j);
Push(&S,i,j);
A[i][j]=3;                                              // 3 = Enter

printf("\n*********************\n");
printf("* The StePs are :-  *");
printf("\n*********************\n");

while((A[i][j]!=2) && (!(isEmpty(S))))                  // 2 = Exit
{
 if(A[i][j+1] == 0 || A[i][j+1] == 2 )                  // go Right
 {
  Push(&S,i,j+1);
  Enqueue(&Q,i,j+1);
//   if(A[i][j]!=3)
   A[i][j]=5;
  printf("Right ,");
  j++;
  (*PathCount)++;
  (*StepCount)++;
 }
 else if(A[i+1][j] == 0 || A[i+1][j] == 2)              // go Down
 {
  Push(&S,i+1,j);
  Enqueue(&Q,i+1,j);
//   if(A[i][j]!=3)
   A[i][j]=5;
  printf("Down ,");
  i++;
  (*PathCount)++;
  (*StepCount)++;
 }
 else if(A[i-1][j] == 0 || A[i-1][j] == 2)              // go Up
 {
  Push(&S,i-1,j);
  Enqueue(&Q,i-1,j);
//   if(A[i][j]!=3)
   A[i][j]=5;
  printf("Up ,");
  i--;
  (*PathCount)++;
  (*StepCount)++;
 }
 else if(A[i][j-1] == 0 || A[i][j-1] == 2)              // go Left
 {                                               
  Push(&S,i,j-1);
  Enqueue(&Q,i,j-1);
//   if(A[i][j]!=3)
   A[i][j]=5;
  printf("Left ,");
  j--;
  (*PathCount)++;
  (*StepCount)++;
 }
 else
 {
  A[i][j]=9;
  Pop(&S);
  i=S->x;
  j=S->y;
  Enqueue(&Q,i,j);
  (*PathCount)--;
  (*StepCount)++;
  printf("Pop ,");
 }
// system("PAUSE");
}
PrintStack(S);
PrintQueue(Q);
}
/*============================================================================*/

//                            ******* Main *******

int main()
{
int A[11][11],n,PathCount,StepCount,i;
printf("\n Enter How Many floor in The Bulding (Number of Files) ?!\n");
scanf("%d",&n);

for(i=0;i<n;i++)
{
 PathCount=0;
 StepCount=0;

 Initialize(A);
 Read(A);
 Print(A);
 EnterMaze(A,&PathCount,&StepCount);

 printf("\nNote :-\n9 = wrong way\n8 = outside\n5 = right way ");
 printf("\n3 = The Enter\n2 = The Exit\n1 = The Wall\n0 = The Way \n\n");

 Print(A);

 printf("\n ****************************** \n");
 printf("\n *    Number of Step = %d     * \n",StepCount);
 printf("\n *    Length of Path = %d     * \n",PathCount);
 printf("\n ****************************** \n");

}

     system("PAUSE");
     return 0;
}


Answer
Just looking at the program, it will be too difficult to say what is the bug.
You will have to give me a set of inputs and corresponding expected outputs. And also tell me what output you are getting now.
These set should contains some which works correctly according to expectations and some which doesn't.

Without this sort of set (Test Cases), I will not be able to help you.

-ssnkumar