The GATE Grind

GATE 2022 CE (CE1) – Question 9

General Aptitude · Analytical Aptitude: Logical Reasoning and Deduction · 2 marks · Multiple choice

In the square grid shown on the left, a person standing at P2 position is required to move to P5 position. The only movement allowed for a step involves, “two moves along one direction followed by one move in a perpendicular direction”. The permissible directions for movement are shown as dotted arrows in the right. For example, a person at a given position Y can move only to the positions marked X on the right. Without occupying any of the shaded squares at the end of each step, the minimum number of steps required to go from P2 to P5 is 1 2 3 4 5 P Q R S T Example: Allowed steps for a person at Y

Labelled grid with shaded forbidden cells and marked start P2 and destination P5. See the attached source image.
  1. 4
  2. 5
  3. 6
  4. 7

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) 5

Explanation

Treat every unshaded cell as a vertex and connect cells by the permitted knight-like moves. Breadth-first search from P2 finds no route of fewer than five steps.

A valid five-step route is **P2 → Q4 → R2 → P3 → R4 → P5**. Every landing cell is unshaded, and each move is two cells along one axis and one along the other. Therefore the minimum is **5 (B)**.