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

Learn moreOpportunities for recent engineering grads.

Apply TodayGiven a matrix of ones and zeros, you must determine if there are any doughnuts present (would Homer Simpson like it?). A doughnut is a 4-connected region of ones completely enclosing a 4-connected region of zeros. You can assume that any regions of ones are either blobs (or genus 0) or doughnuts (genus 1). Thus if you find any hole in a region of ones, it is a doughnut. Also, there are no nested doughnuts.

Return true if any doughnuts are present, otherwise false.

Examples:

This is a doughnut:

1 1 1 1 0 1 1 1 1

Here is another doughnut:

0 0 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 1 1 1 1

This is not a doughnut:

0 1 0 1 0 1 0 1 0

because the ones are not 4-connected and so can't surround anything.

7 correct solutions
30 incorrect solutions

Last solution submitted on Apr 11, 2014

4 Comments