0

Greetings.

I have an 2-D array of size [N][N] which will represent a rectangular area / map with N rows and N columns.

Let's say I pick the middle as starting point (or anywhere else), I want to walk through all elements with the constraint of moving only X times before having to reset back to starting point. I then can walk through the path I've went to, but that will waste a turn.

I'm just wondering if there is a specific algorithm for this problem so I can compare with my current way of doing which just stores the moves I already did. (quite messy tbh)

Thanks in advance.

2
  • What's the question? Do you want to know what the minimum X for a given N can be, and what the associated algorithm is?
    – David Z
    Mar 16, 2009 at 7:22
  • The minimum X is not such an interesting question... X has to be at least enough for him to reach the furthest point, which would be approximately N if he starts in the center and 2N if he starts in a corner. I think he wants an algorithm that covers the board in the minimum number of walks. Hmm.. Mar 17, 2009 at 6:40

2 Answers 2

1

It looks like you're talking about a turn-based game? So I think you should not look at them as turns, but look at objectives, than use a path finding algorithm to see how many steps away the objective is, than assume the objectives have a value and divide that by the amount of turns needed to get to that objective and chose the highest result as your current destination, the next turn you'll have to rethink your strategy again.

I tried to make my answer more clear, do the following for each turn.

  1. Determine the value of the objectives
    • Determine the amount of steps needed to reach the objective using a path finding algorithm.
    • Calculate the amount of turns needed (Math.Ceil(steps / stepsPerTurn))
    • Determine the object with highest value for the least amount of turns.
    • Travel to that objective.
-1

Heres a strategy which is not optimal, but it's easy, reasonably efficient, and you don't need to keep a big storage list or do fancy computing or coding.

Start at your current point, and walk right until a wall. Step down, walk left. Keep zig-zagging back and forth. If you reach the bottom, start over and zig-zag cover the top half in a similar way.

If you run out of steps doing your painting, just walk straight towards the location you were at before, and continue painting.

This algorithm is not optimal, but it's likely 10 lines of code and 2 variables.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.