Angels vs Devils

Moderate
0/80
profile
Contributed by
2 upvotes
Asked in company
MindInventory

Problem statement

In a chessboard(‘N’ x ‘N’) game of Angles(‘A’) and Demons(‘O’, ‘X’, and ‘Z’), various demons try to kill the angel whose aim is to get across from one end of the board to the opposite end of the board. There are 3 different devils having different powers.

Starting point of Angel can only be on the border but not the corners of the board. He will walk in a straight line(horizontal or vertical only) across the board, one cell every second.

The powers of various devils are as follows:-

OGRE(‘O’): Cannot move but he can kill with his breath. His powers change with time: 
In 1st second ‘O’ can kill the angel if the ‘A’ reaches the ogre’s location.
In the 2nd second, ‘O’ can kill if ‘A’ is in 8 surrounding cells.
In 3rd second ‘O’ can kill if ‘A’ reaches the ogre’s location.
In the 4th second, ‘O’ cannot kill ‘A’ in any condition.
This sequence repeats cyclically.
XILL(‘X’): He has the power to kill an angel only if 
‘A’ is the same colored cell as ‘X’.
‘X’ is only active at the time equal row number of ‘X’.

ZAHHAK(‘Z’): He leaves a poison trail and moves in the ‘Z’ shape. His first move is ‘down’ and then ‘right’ and keeps on making a trail in that order until he reaches the border. If he reacher a border, he changes his direction of movement to the opposite direction he came from. Angel coming on poison will die immediately.

You need to tell the coordinate of the cell at which the angel will die or output [-1, -1] if Angel successfully crosses the board.

EXAMPLE: 
Input: 
'N' = 12
‘A’ = [12 11]
‘O’ = [3, 9]
‘X’ = [8, 4]
‘Z’ = [4, 3]

Output: [5, 11]

The Angel will be killed by the demon(‘X’) at 8th second as follows:

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', the number of test cases. For each test case

In the first line of each test case, an integer ‘N’ denotes the size of the board.
The Next four lines contain two integers each denoting the coordinates of Angel(‘A’) and demons(‘O’, ‘X’, and ‘Z’) respectively.
Output format : 
For each test case, print the co-ordinating of the Angles death or print [-1, -1] if Angel successfully crosses the board.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= 'T' <= 10
5 <= 'N' <= 500
1 <= ‘A[i], A[j]’ <= ‘N’
1 <= ‘O[i], O[j]’ <= ‘N’
1 <= ‘X[i], X[j]’ <= ‘N’
1 <= ‘Z[i], Z[j]’ <= ‘N’
Where ‘i’ and ‘j’ represent the row and column respectively.

Time Limit: 1 sec
Sample Input 1 :
2
12
12 11
3 9
8 4
4 3
12
12 9
10 2
3 7
2 11
Sample Output 1 :
5 11
-1 -1
Explanation Of Sample Input 1 :
The Angel will be killed by the demon(‘X’) at the 8th second as follows:


The Angel will not be killed by anyone as the demon ‘X’ and angel will be on different color cells at the time of activation of demon ‘X’, and the demon ‘Z’ will not cross paths with the angel during the time of 12 seconds and demon ‘O’ will never reach angel.
The picture depicts the board at ‘T’ = 3.

Sample Input 2 :
2
5
4 1
2 4
5 5
1 1
5
4 1
2 4
5 5
4 1
Sample Output 2 :
-1 -1
4 1
Hint

The angel only needs ‘N-1’ seconds to cross the board.

Approaches (1)
Greedy Approach

Approach: 
 

  1. As the angel only needs ‘N’ seconds to cross the board we just have to check for each second, whether it can be killed by any demon or not?
  2. Precalculate the cells the monster ‘Z’ is going to visit at a time ‘t’.
  3. Check for monster ‘X’ if the angel ‘A’ is in the same type of cell as ‘X’ at a time ‘t’ = X[i], where ‘i’ = row number of ‘X’.
  4. Make the angel move from starting position to destination and check for each position if it can be attacked by monster ‘O’ or if it is in the cell poisoned by monster ‘Z’ at some time in the past or at that time.
     

Algorithm :  
 

  • Create a direction vector pair ‘D’ for monster ‘Z’ for determining the direction of movement for ‘Z’ at the next second.
  • Create and initialize an array ‘ZT’(time of poisoning of ‘Z’) of size ‘N’ x ‘N’ with some large value greater than ‘N’.
  • Do a for loop on ‘TIME’ = 0 to ‘N’
    • If the next cell according to ‘D’ is not within the board boundary, then:
      • Change the direction array ‘D’ according to the instructions mentioned in the question, in order to move to a valid cell.
    • Move ‘X’ to the next cell.
  • Create a valid function to check if the next cell of the move is within board boundaries.
  • Create and initialize a ‘T’ array of size ‘N’ x ‘N’ with values ‘0’ to store the cells poisoned by monster ‘O’ at some time ‘t’
  • Create an array ‘DX’ with values = [1, 0, -1, 0, -1, -1, 1, 1] and
  • Array ‘DY with values = [0, 1, 0, -1, -1, 1, -1, 1]
  • Run a for loop from ‘0’ to the time it takes to reach other end, to check the safety of ‘A’ at a time ‘i’:
    • If ‘I’ == ‘X[i]’
      • If the type of cell of ‘A’ is equal to the type of cell of ‘X’
        • Return current coordinates of ‘A’.
    • If ‘i’ modulo ‘4’ is equal to ‘3’ then subtract ‘3’ from the cell (O[i], O[j]) of ‘T’ to remove the effect of monster ‘O’ from its cell.
    • Else increase the count of cell (O[i], O[j]) in ‘T’.
    • If ‘i’ modulo ‘4’ == 1 then,
      • Increase the count of all the neighboring cells of monster ‘O’ by ‘1’ using ‘DX’ and ‘DY’ in ‘T’.
    • Check if the current cell of ‘A’ has already been poisoned by ‘Z’ or not or is in the attack range of ‘O’ using array ‘T’
      • If true then return the current cell.
    • If ‘i’ modulo ‘4’ == 1 then,
      • Decrease the count of all the neighboring cells of monster ‘O’ by ‘1’ using ‘DX’ and ‘DY’ in ‘T’.
    • Move the angel to the next cell.
  • Return ‘[-1, -1]’
Time Complexity

O(N * N), Where ‘N’ is the row, column length of the board.

Creating the boards of size ‘N’ * ‘N’ takes ~N time, the time complexity will be O(N * N)

Space Complexity

O(N * N), Where ‘N’ is the row, column length of the board.


As we are using the extra ‘ZT’ and ‘T’ array of size ‘N * N ’, the space complexity will be O(N * N).

Code Solution
(100% EXP penalty)
Angels vs Devils
Full screen
Console