Problem 1907. Capture the flag(s)
Flags are distributed randomly on a large board. Starting from the corner position your goal is to capture as many flags as possible in at most N moves.
Description:
The board is described by a matrix B with 1's at the flag positions, and 0's otherwise.
E.g.
B = [0 0 1 1; 0 0 1 1; 0 0 1 0];
N = 6;
You are starting at the top-left corner (row=1, col=1) and are allowed N steps (steps are up/down/left/right movements, no diagonal movements allowed).
Return a trajectory attempting to maximize the number of flags captured. The output of your function should be a Nx2 matrix of the form [row, col] (not including the initial [1,1] position) visiting as many flags as possible.
E.g.
path = [1 2; 1 3; 1 4; 2 4; 2 3; 3 3];
This solution captures all 5 flags on the board.
Scoring:
Your function will receive a score equal to the number of non-visited flags across all 50 of the testsuite problems. You need to leave at most 10,000 flags univisited (among 50,000 total flags) to pass this problem.
Note:
The boards and number of movements allowed will be large. Optimizing over all possible trajectories is very likely to time out.
Solution Stats
Problem Comments
-
1 Comment
I love the fact that you put an animation option in. It's not just helpful to see where your heuristic is messing up, it's fun to watch too.
Solution Comments
Show commentsProblem Recent Solvers6
Suggested Problems
-
Pythagorean perfect squares: find the square of the hypotenuse and the length of the other side
56 Solvers
-
Back to basics 13 - Input variables
267 Solvers
-
Back to basics 17 - white space
271 Solvers
-
Determine if input is a Narcissistic number
200 Solvers
-
233 Solvers
More from this Author38
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!