/****************************************
* Section : 10
* Roll No. : 20CS10000 / 20CS30000
* Name : Aritra Hazra
* Assignment No : 5A
* Description : Police Catching Murderer
* Date : 01-Jun-2021
****************************************/

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

#define MAX_POLICE 1000

// determine new position in tree after a movement has taken
int NewPos(int position, char move, int gridLength)
{
  if( (move == 'L') && (position%gridLength != 1) )
    return position-1;
  if( (move == 'R') && (position%gridLength != 0) )
    return position+1;
  if( (move == 'U') && (position > gridLength) )
    return position-gridLength;
  if( (move == 'D') && (position <= gridLength*(gridLength-1)) )
    return position+gridLength;
  //else move == 'S'
  return position;
}

// initialize all array elements to 1
void OneOutArray(int array[], int length)
{
  int i;
  for(i = 0; i < length; i++)
  {
    array[i] = 1;
  }
}

//returns the index at which the Murderer was caught or 0 if not caught
int murdererCaughtPosition(int polices[], int numPolices, int murdererIndex)
{
  int i;
  for(i = 0; i < numPolices; i++)
  {
    if(polices[i] == murdererIndex)
      return i+1;
  }
  return 0;
}

int main() {
  int gridLength = 0;
  int numPolices = 0;
  int numMoves = 0;
  int murdererIndex = 0;
  char turn[MAX_POLICE + 2]; // assuming max 1000 Polices and 1 Murderer
  int tempPos = 0;
  int catchCheck = 0;
  int murdererCaught = 0;
  int police[MAX_POLICE];
  int i, j, k;
  
  printf("Input: ");
  //initialize tree positions
  scanf("%d %d %d %d", &gridLength, &numPolices, &numMoves, &murdererIndex);
  OneOutArray(police, numPolices);

  printf("\nMovements:");
  printf("\n\t-- Murderer's Initial Position: %d", murdererIndex);
  printf("\n\t-- Polices' Initial Position:");
  for(i=0; i<numPolices; i++){
    printf(" %d", police[i]);
  }
  
  if(murdererIndex == 1) { // caught at initial location of police
    printf("\nOutput: 0 1 1");
    murdererCaught = 1;
  }
  else { // murderer not at the initial location of police
    for(j=0; j< numMoves; j++) {
      scanf("%s", turn);

      // checking if the murderer caught after (s)he moves
      tempPos = NewPos(murdererIndex, turn[0], gridLength);
      murdererIndex = tempPos;
      
      // new grid position of the murderer after murderer moves
      printf("\n\t-- Murderer moves to Position: %d\n", murdererIndex);

      catchCheck = murdererCaughtPosition(police, numPolices, murdererIndex);
      if(catchCheck > 0) { // murderer caught
        printf("\nOutput: %d %d %d", j+1, catchCheck, murdererIndex);
        murdererCaught = 1;
        break;
      }

      // checking is the murderer caught after polices move
      for(k=0; k < numPolices; k++) { // determine new positions for all polices
        tempPos = NewPos(police[k], turn[k+1], gridLength);
        police[k] = tempPos;
      }
      
      // new grid positions of the polices after polices move
      printf("\t-- Polices move to Position::");
      for(i=0; i<numPolices; i++){
        printf(" %d", police[i]);
      }
      
      catchCheck = murdererCaughtPosition(police, numPolices, murdererIndex);
      if(catchCheck > 0) { // murderer caught
        printf("\nOutput: %d %d %d", j+1, catchCheck, murdererIndex);
        murdererCaught = 1;
        break;
      }
    }
  }
  if(!murdererCaught) { // murderer escaped
    printf("\nOutput: 0 0 0");
  }
  printf("\n");

  return 0;
}