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 502. Would Homer Like It?

Created by Ned Gulley

Given 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.

Tags

Problem Group

Solution Statistics

7 correct solutions 30 incorrect solutions
Last solution submitted on Apr 11, 2014

Problem Comments