IAE Academy

GATE 2022 BT GA Q.9: solution and answer

GATE 2022 · BTGA Q.9 · 2 marks · MCQ

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

GATE 2022 BT GA question 9: Left: a 5x5 square grid with columns labelled 1 to 5 across the top and rows labelled P, Q, R, S, T down the left side.Tap to open full size
Figure from the GATE 2022 BT paper. It is part of the question.
Figure description

Left: a 5x5 square grid with columns labelled 1 to 5 across the top and rows labelled P, Q, R, S, T down the left side. Shaded (dark) squares: P1, P4, Q3, R1, S2, S5, T3. A smiley face marks the start at P2. Right: a 5x5 grid with the person Y at the centre square (row 3, column 3), with a cross of four arrows (up, down, left, right) drawn beside it. Dotted arrows from Y go two squares along one direction and then one square perpendicular, ending at eight squares marked X: (row 1, col 2), (row 1, col 4), (row 2, col 1), (row 2, col 5), (row 4, col 1), (row 4, col 5), (row 5, col 2), (row 5, col 4). Caption: Example: Allowed steps for a person at Y.

  1. (A)

    4

  2. (B)

    5

  3. (C)

    6

  4. (D)

    7

Answer and solution

ANSWER

The minimum number of steps from P2 to P5 is 5, which is option (B).

Official answer: BSource: Official answer key, GATE 2022 BT (IIT Kharagpur)

  1. Each step is a knight move: two squares in one direction, then one square perpendicular. Label squares by row P, Q, R, S, T (rows 1 to 5) and column 1 to 5. Shaded squares: P1, P4, Q3, R1, S2, S5, T3. A step may jump over a shaded square, but it must not end on one.

  2. Work backwards from P5. The knight squares from which P5 can be reached are Q3 and R4. Q3 is shaded, so the last step must start at R4.

  3. The knight squares around R4 are P3, P5, Q2, S2, T3 and T5. S2 and T3 are shaded and P5 is the target. So R4 can be reached only from P3, Q2 or T5.

  4. Work forwards from P2. The knight squares from P2 are R1, R3 and Q4. R1 is shaded, so step 1 ends at R3 or Q4.

  5. Step 2 from R3 gives T2, T4, Q1, Q5 and S1. The move to S5 is blocked because S5 is shaded, and the move to P4 is blocked because P4 is shaded. Step 2 from Q4 gives S3 and R2, and also P2, which is the start. So the squares reached after 2 steps are T2, T4, Q1, Q5, S1, S3 and R2. None of P3, Q2 or T5 is among them, so R4 cannot be reached in 3 steps.

  6. Step 3: Q1 goes to P3. S1 goes to Q2. S3 goes to T5. So P3, Q2 and T5 are first reached at step 3.

  7. Step 4: P3, Q2 or T5 goes to R4. Step 5: R4 goes to P5.

  8. R4 cannot be reached before step 4, so P5 cannot be reached before step 5. The minimum number of steps is 5.

KEY IDEA

Treat each move as a knight move. Work backwards from the target to find the only squares it can be reached from. Then run a breadth-first search forward from the start, skipping squares that are shaded at the end of a step.

WATCH OUT FOR

Treating shaded squares as walls that cannot be jumped over, or checking only the end-point and missing that P5 can be entered only from R4 because Q3 is shaded. Another slip is adding a move that is not a knight move, for example T2 to P3, which would give a path that is too short.

From the GATE 2022 BT paper. Every question of this paper · Download the full paper · All 72 Reasoning questions, with notes

More Reasoning questions