// Rat-in-a-maze by stack DFS using clockwise search of NESW.
// Note:   Positions are given as 1..rows and 1..cols.
//         Walls are placed around the maze, i.e. additional rows and cols.
// Input:  Dimensions m (rows) and n (columns).
//         Start position as row and column.
//         Final position as row and column.
//         Each wall as row and column.

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

int maze[81][81];
int rows,cols;
int startRow,startCol,stopRow,stopCol;

void printMaze()
{
int i,j;

for (i=0;i<=rows+1;i++)
{
  for (j=0;j<=cols+1;j++)
  {
    switch (maze[i][j]) {
      case 0:
        printf(" "); // Open space, never discovered
        break;
      case 1:
        printf("."); // Wall
        break;
      case 2:
        printf("^"); // Dead end path
        break;
      case 3:
        printf("#"); // Path between start and stop
        break;
      default:
        printf("\nFatal at %d\n",__LINE__);
        exit(0);
    }
    printf(" ");
  }
  printf("\n");
}
}

void readInput()
{
int i,j;

scanf("%d %d",&rows,&cols);
// Walls for rows 0 and rows+1
for (j=0;j<=cols+1;j++)
  maze[0][j]=maze[rows+1][j]=1;
// Walls for columns 0 and cols+1
for (i=1;i<=rows;i++)
  maze[i][0]=maze[i][cols+1]=1;
// Clear out interior of maze
for (i=1;i<=rows;i++)
  for (j=1;j<=cols;j++)
    maze[i][j]=0;
scanf("%d %d",&startRow,&startCol);
if (startRow<1 || startRow>rows || startCol<1 || startCol>cols)
{
  printf("Fatal at %d\n",__LINE__);
  exit(0);
}
scanf("%d %d",&stopRow,&stopCol);
if (stopRow<1 || stopRow>rows || stopCol<1 || stopCol>cols)
{
  printf("Fatal at %d\n",__LINE__);
  exit(0);
}
if (startRow==stopRow && startCol==stopCol)
{
  printf("Fatal at %d\n",__LINE__);
  exit(0);
}
while (scanf("%d %d",&i,&j)!=EOF)
{
  if (i<1 || i>rows || j<1 || j>cols)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  if (i==startRow && j==startCol || i==stopRow && j==stopCol)
  {
    printf("Fatal at %d\n",__LINE__);
    exit(0);
  }
  maze[i][j]=1;
}
}

typedef enum {init,north,east,south,west} direction;
typedef struct {
  int row,col;
  direction current;
} stackEntry;
stackEntry stack[81*81];  // Bound on stack size?
int sp=(-1);  // stack is empty

int emptyStack()
{
return sp==(-1);
}

void pushStack(stackEntry x)
{
stack[++sp]=x;
}

stackEntry popStack()
{
return stack[sp--];
}

int DFS(int row,int col)
{
stackEntry work;
int returnValue;

work.row=row;
work.col=col;
work.current=init;
pushStack(work);
while (!emptyStack())
{
  work=popStack();
  if (work.current==init)  // Just arrived here?
  {
    if (maze[work.row][work.col]!=0)  // Not an open slot?
    {
      returnValue=0;
      continue;
    }
    if (work.row==stopRow && work.col==stopCol)  // At destination?
    {
      maze[work.row][work.col]=3;
      returnValue=1;
      continue;
    }
    maze[work.row][work.col]=2;  // Mark slot as discovered
  }
  else if (returnValue==1)  // Backtracking from successful search?
  {
    maze[work.row][work.col]=3;
    continue;
  }
  else if (work.current==west)  // No other directions to try
  {
    returnValue=0;
    continue;
  }
  // Try next direction.  Push current position and new position
  work.current++;
  pushStack(work);
  switch (work.current) {
    case north:
      work.row--;
      break;
    case east:
      work.col++;
      break;
    case south:
      work.row++;
      break;
    case west:
      work.col--;
      break;
  }
  work.current=init;
  pushStack(work);
}

return returnValue;
}

main()
{
readInput();
printf("Initial maze:\n");
printMaze();
if (DFS(startRow,startCol))
  printf("Success:\n");
else
  printf("Failure:\n");
printMaze();
}