GATE CE 2022 Set 1 — Question 9

The movement described is identical to a knight's move in chess (an 'L' shape: 2 squares in one cardinal direction and 1 square perpendicular). Let's denote the grid positions by (Row, Column).
Start: P2 = (1, 2)
Target: P5 = (1, 5)
Shaded (blocked) squares: P1(1,1), P4(1,4), Q3(2,3), R1(3,1), R5(3,5), S2(4,2), S4(4,4), T3(5,3).We need to find the shortest path from (1, 2) to (1, 5) avoiding blocked squares.Step 1: From P2(1, 2), possible moves are Q4(2, 4) and R3(3, 3). Both are unshaded.
Let's try P2(1, 2) $\rightarrow$ Q4(2, 4).Step 2: From Q4(2, 4), possible moves are S3(4, 3), S5(4, 5), P2(back), P6(out). S3 and S5 are unshaded.
Let's try Q4(2, 4) $\rightarrow$ S3(4, 3).Step 3: From S3(4, 3), possible moves are T5(5, 5), T1(5, 1), Q1(2, 1), Q5(2, 5), R5(blocked), R1(blocked), P2(back), P4(blocked).
Let's try S3(4, 3) $\rightarrow$ T5(5, 5).Step 4: From T5(5, 5), possible moves are R4(3, 4) and S3(back). R4 is unshaded.
Let's try T5(5, 5) $\rightarrow$ R4(3, 4).Step 5: From R4(3, 4), possible moves are P3(1, 3), P5(1, 5), T3(blocked), T5(back), Q2(2, 2), Q6(out), S2(blocked), S6(out).
Target P5(1, 5) is reached in this step.Path: P2(1,2) $\rightarrow$ Q4(2,4) $\rightarrow$ S3(4,3) $\rightarrow$ T5(5,5) $\rightarrow$ R4(3,4) $\rightarrow$ P5(1,5).
Total steps = 5.Checking other paths will show that 5 is the minimum number of steps required to reach the target while avoiding shaded squares.