Author |
Topic: Smallest number of moves (Read 1207 times) |
|
valerie_parker
Newbie
Posts: 5
|
 |
Smallest number of moves
« on: Feb 1st, 2006, 5:26pm » |
 Quote  Modify
|
I got the following problem as a class assignment, and i was wondering if anyone has any ideas on it. Or if someone can point me in the direction of a similar problem. I only recently found this site and forum. Have to try some of these puzzles myself... as soon as I finish this assignment. I have some ideas, there at the bottom. Am I going in the right direction?
~~~~~~~~~~~
A rectangular board is divided into M rows and N columns (2 <= M, N <= 100). A robot jumps from one square x to another square y as follows: from x, it moves p squares, either horizontally or vertically, and then it moves q squares in a direction perpendicular to the previous to get to y. It can move horizontally either to the left or to the right and vertically either up or down. (A robot move is similar to a knight move in chess with p = 2 and q = 1).
Assume that the top-left square is (1, 1) and the bottom-right square is (M, N). The robot is put in the square with coordinates (X, Y) (1 <= X <= M, 1 <= Y <= N) .
The robot wishes to get to a different square (U, V) (1 <= U <= M, 1 <= V <= N) using only the jumps described above. It is required to find the minimal number, S, of jumps needed to get to (U, V) and the sequence of squares visited in reaching (U, V). If there is more than one sequence, you need find only one. If it is not possible to get to (U, V) from (X, Y), print an appropriate message.
For example, consider a board with 7 rows and 4 columns, with p = 2, q = 1. Suppose the robot starts in square (3, 1) and it needs to get to square (6, 1). It can do so in 3 moves by jumping to (5, 2) then (7, 3) then (6, 1).
Write a program which reads values for M, N, p, q, X, Y, U, V in that order and solves the problem.
You may not use any pre-defined data structures such as stacks, queues or linked lists.
~~~~~~~~~~~
My ideas:
I have an MxN array, called T, initialised to -1, and the start position as 0. I'm thinking about a recursive solution. I make the recursive call using the 8 possible directions the robot can move from a sqaure, can the number of moves to that position.
If the location falls out of the rectangle, it returns. If T[i][j] = -1, or T[i][j] > currentNumberOfMoves, then the current number of moves to that location is the smallest, and set T[i][j] to this number.
I haven't thought the whole thing through as yet, as I only got it yesterday and I really didnt get the time to write out a proper algorithm. Just decided to throw it out to see if any one can give any ideas.
thanks!
|
|
 IP Logged |
|
|
|
ChunkTug
Full Member
Gender: 
Posts: 166
|
|
Re: Smallest number of moves
« Reply #1 on: Feb 1st, 2006, 8:56pm » |
Quote Modify
|
That sounds right to me.
One thing to remember is that when you've found that minimum number of moves you need to have the sequence of moves as well. Consider storing more than just the minimum number of moves in the array and how that could be used to reconstruct the path.
|
| « Last Edit: Feb 1st, 2006, 8:57pm by ChunkTug » |
IP Logged |
|
|
|
Neelesh
Junior Member
Gender:
Posts: 147
|
|
Re: Smallest number of moves
« Reply #2 on: Feb 1st, 2006, 11:03pm » |
Quote Modify
|
Seems similar to Breadth-First Search in a graph. (p,q) is "adjacent" to (p',q') iff the robot can jump from (p,q) to (p',q') in a single step. You can use the usual "coloring" technique (CLRS) to avoid cycles.
|
|
IP Logged |
|
|
|
KWillets
Junior Member
Posts: 84
|
|
Re: Smallest number of moves
« Reply #3 on: Feb 2nd, 2006, 9:49am » |
Quote Modify
|
on Feb 1st, 2006, 8:56pm, ChunkTug wrote:That sounds right to me.
One thing to remember is that when you've found that minimum number of moves you need to have the sequence of moves as well. Consider storing more than just the minimum number of moves in the array and how that could be used to reconstruct the path. |
|
There's a method from dynamic programming for finding one minimal path in the array by backtracing after the end is reached. I won't give it away except to say that each hop should be fairly obvious. Do some reading on edit distance or Smith-Waterman to get full credit.
Also, reverse the problem to get the right output order. 
|
|
IP Logged |
|
|
|
valerie_parker
Newbie
Posts: 5
|
|
Re: Smallest number of moves
« Reply #4 on: Feb 2nd, 2006, 10:09am » |
Quote Modify
|
Hey, thanks all, for the help. I'll get started on this right away, along with the necessary reading .
Thanks again!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print