/* Problem 6--Magical Protection
   The easiest way to handle this was to place boundaries all around
   Dumbledore's location and solve this like a typical maze */

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

#define MAX 20

int main (int argc, char **argv);
int Process (void);
void getRC (char *pos, int *r, int *c);
void Advance (int *r, int *c);

FILE *in, *out;
char MZ[MAX+2][MAX+2]; /* put row of boundaries all around maze */
int col, row;

int main (int argc, char **argv) {

  char A[MAX+2];

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 while (1) {
  fgets (A,MAX+2,in); /* read in first line of maze */
  if (A[0]=='\n') break;
  memset (MZ,'1',sizeof MZ); /* fill maze up with boundaries */
  col = strlen (A)-1; /* compute number of columns */
  memcpy (&MZ[1][1],A,col); /* fill in first row */
  row = 1;
  while (1) {
   fgets (A,MAX+2,in); /* read in next row */
   if (A[0]=='\n') break;
   memcpy (&MZ[++row][1],A,col); /* copy next row into maze */
  }
  if (Process ())
   fprintf (out,"Voldemort can kill Harry.\n");
  else
   fprintf (out,"Voldemort cannot kill Harry.\n");
 }
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process detects whether Voldemort can make it to Harry */

int Process (void) {

  int hr, hc, vr, vc, dr, dc, i, j, r, c;

 getRC (strchr ((char *)MZ,'H'),&hr,&hc); /* Get positions of major */
 getRC (strchr ((char *)MZ,'V'),&vr,&vc); /* players */
 getRC (strchr ((char *)MZ,'D'),&dr,&dc);
 for (i=dr-1;i<=dr+1;i++)  /* Put boundaries all around Dumbledore */
  for (j=dc-1;j<=dc+1;j++)
   MZ[i][j] = '1';  /* If Harry or Voldemort are now boundaries, it */
 if (MZ[vr][vc]=='1'||MZ[hr][hc]=='1') return 0; /* cannot be done. */
 MZ[hr][hc] = MZ[vr][vc] = '0'; /* Make Harry and Voldemort empty */
 r=vr;c=vc;                     /* squares. */
 while (1) {/* go through maze starting from Voldemort's square */
  if (r==hr && c==hc) return 1; /* I'm on Harry's square */
  if (MZ[r][c]=='*') return 0; /* If I've exhausted all paths */
  Advance (&r,&c); /* Move one square */
 }
}

/* getRC gets the position of a character in the array */

void getRC (char *pos, int *r, int *c) {

  int ri = pos-(char *)MZ; /* raw index of the character */

 *r = ri/(MAX+2); /* Compute row and column */
 *c = ri%(MAX+2);
}

/* Advance moves one square in the maze.  It first tries to visit a
   previously unvisited square.  If it can, it marks the path it took to
   get there.  If it can't visit a new square, it backtracks to its
   previous square, and marks the square as a dead end. */

void Advance (int *r, int *c) {

    /* Where can I find a new square? */
 if (MZ[*r-1][*c] == '0') {MZ[*r][*c]='N';(*r)--;return;}
 if (MZ[*r+1][*c] == '0') {MZ[*r][*c]='S';(*r)++;return;}
 if (MZ[*r][*c-1] == '0') {MZ[*r][*c]='W';(*c)--;return;}
 if (MZ[*r][*c+1] == '0') {MZ[*r][*c]='E';(*c)++;return;}
    /* How do I backtrack? */
 if (MZ[*r-1][*c] == 'S') {MZ[*r][*c]='*';(*r)--;return;}
 if (MZ[*r+1][*c] == 'N') {MZ[*r][*c]='*';(*r)++;return;}
 if (MZ[*r][*c-1] == 'E') {MZ[*r][*c]='*';(*c)--;return;}
 if (MZ[*r][*c+1] == 'W') {MZ[*r][*c]='*';(*c)++;return;}
 MZ[*r][*c]='*';  /* I'm boxed in! */
}