Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

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.

Tags

Problem Group

Solution Statistics

9 correct solutions 5 incorrect solutions
Last solution submitted on May 07, 2014

Problem Comments

Solution Comments