Hard Divide and Conquer > Dynamic Programming

Mr Papon doesn’t like Nasir at all. So he always try to give Nasir hard problem to solve. Today Mr Papon comes with knight and chess board problem. Given the size of the chess board ( **N X N** ) and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board of **N X N** . Nasir isn’t very good at probability . Can you please help him. Note:- 1) The knight makes its all 8 possible moves with equal probability. 2) Once the knight is outside the chess board it cannot come back inside. ![enter image description here][1] Input: ------ The first line contains an integer T( 1<= T <= 100 ) which denotes the number of Test cases. T test cases follow . Each test case consists of two line. At first there are two integers N and K. and second there are two integers x , y which represents the initial position of the knight. Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the probability that after k moves the knight will be inside the chess board. Print answer with 4 decimal number after point. Check sample Input and Output for better understanding. Constraints: -------------- 1<= T <= 100 1 <= N <= 100 1 <= K <= 100 1 <= ( x , y ) <= N Sample Input ---------------- 2 8 3 3 5 10 3 2 4 Sample Output ------------- Case 1: 0.5742 Case 2: 0.4648 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/c587e5cf-af84-c11f-ba0d-08d40e38b120_3fcd62a33dbf4069b8e946ee44c11f61_W626xH264.png

Shakil Ahmed