I like games. One of my favorite games is \"number grid\", and the mechanics are

Question

I like games. One of my favorite games is "number grid", and the mechanics are as follows: We are given an m times n grid of positive integers A (except for one cell, mentioned below), indexed from 1 torn for the rows, and 1 to n for the columns. We start at cell (1, 1). At any turn, we choose to move right, down, up, or left: however, we must move (in a direction) exactly by the number in the currently viewed cell. If the number on the square is too large for any direction to move, we can choose to wrap around the grid in modulo fashion. For example, if m = n = 5, we are at cell (2, 3) and it has value 6, then moving down will put us at cell ((2 + 6) mod 5, 3) = (3, 3). The other three cardinal directions are handled similarly. Our goal is to reach the only special cell, at a given location where (i, j) notequalto (1, 1), in the fewest moves possible. Design an efficient algorithm that, given such a grid A, returns the smallest number of moves to reach the special cell: if this task is not possible, the algorithm then correctly reports 0.

Explanation / Answer

1. Choose m and n for grid formation.

2. Choose i and j which is the current position cell.

3. Calculate i*j.

4. Now choose where we want to go up or down or left or right.

5. If up is chosen, again check if i > 1 then cell will be ( ( i*j - i ) mod m, j) else return 0.

If down is chosen, again check if i < m then cell will be ( ( i*j + i ) mod m, j) else return 0.

If left is chosen, again check if j > 1 then cell will be ( i, ( i*j - j ) mod n) else return 0.

If right is chosen, again check if j < n then cell will be ( i, ( i*j + j ) mod n) else return 0.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.