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
Solution Comments
Show comments
Loading...
Problem Recent Solvers7
Suggested Problems
-
Select every other element of a vector
36160 Solvers
-
2416 Solvers
-
4562 Solvers
-
Compute a dot product of two vectors x and y
1050 Solvers
-
572 Solvers
More from this Author33
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
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.