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 294. A stroll on the beach: finding a route round a connected region

Created by David Young

You are standing on the beach of an island, which you must explore by walking all the way round its coast. Each step is in one of the four directions north, south, east or west, and you must travel clockwise, keeping the sea on your left.

The island is represented by a "blob" of non-zero elements in an array, completely surrounded by zeros representing the sea. All the elements in the blob are 1, except for a single 2 giving your starting and finishing point. Each step takes you to one of the positions in the von Neumann neighbourhood of your current position. Your function must return your steps as a string of the characters N, E, S and W. (N is towards the top of the array as printed, E to the right, etc.) The route must visit every non-zero element that has a 0 as one of its nearest 8 neighbours, and it must not visit any other elements. An element may need to be visited more than once.

The start position will have a 0 as one its nearest 4 neighbours, and the direction of the first step from it will not be ambiguous.

Examples:

Input array = [0 0 0 0 0 0
               0 2 1 1 0 0
               0 1 1 1 1 0
               0 0 0 0 0 0]
        Route = EESEWWWN
Input array = [0 0 0 0
               0 1 1 0
               0 2 0 0
               0 0 0 0];
        Route = NEWS

This is an example of finding a chain code description of a 4-connected shape.

The reference solution has a size of 140.

Problem Group

Solution Statistics

36 correct solutions 24 incorrect solutions
Last solution submitted on Apr 17, 2014

Problem Comments

Solution Comments