Problem 45432. Pitting corrosion on a metal plate: Find the largest pit

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>You are given an N x M matrix of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>ones</w:t></w:r><w:r><w:t> and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>zeros</w:t></w:r><w:r><w:t>, which represents an image of a rectangular metal plate taken from the hull of a ship. Each element of the matrix denotes an area of the plate: The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>ones</w:t></w:r><w:r><w:t> denote areas where the plate has corroded visibly, whereas</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>zeros</w:t></w:r><w:r><w:t> are areas where the metal is still in good condition. The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> (the matrix elements with</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>ones</w:t></w:r><w:r><w:t>) can be found at multiple points on the metal plate.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A collection of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> that are next to each other is called a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>pit</w:t></w:r><w:r><w:t>. Pits can come at different sizes, depending on how much they grew over the years. Pitting corrosion is important to quantify because it gives an idea of the reliability of the ship structure.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For this problem, a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>pit</w:t></w:r><w:r><w:t> is defined more clearly as follows: Two</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> at [row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>R1</w:t></w:r><w:r><w:t>, column</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>C1</w:t></w:r><w:r><w:t>] and [row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>R2</w:t></w:r><w:r><w:t>, column</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>C2</w:t></w:r><w:r><w:t>] belong</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>to the same pit</w:t></w:r><w:r><w:t> if and only if</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>max(abs(R1-R2),abs(C1-C2)) &lt;= 1</w:t></w:r><w:r><w:t>. In other words, if two</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> are adjacent horizontally, vertically, or diagonally, then both are considered to belong to the same pit.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The size of a pit is equal to the number of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> (or</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>ones</w:t></w:r><w:r><w:t>) that belong to it.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Write a function that accepts a matrix X denoting the image in question. Output the size of the largest pit in this image. You are ensured that the size of the matrix is constrained at 1 &lt;= N &lt;= 20 and 1 &lt;= M &lt;= 20.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>As an example, consider the following 10 x 10 image (left). The</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>corroded areas</w:t></w:r><w:r><w:t> that belong to the same pit are then labeled, showing that the largest pit is Pit 1, with a size of 6 (right). In contrast, Pits 2, 3, 4 and 5 have size 2, 2, 4, and 4, respectively.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Sample test case:\nX = [0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0\n 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0\n 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 4 4 0\n 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 4 4 0\n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0\n 0 0 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 5 0 0\n 0 0 0 1 0 0 0 1 1 0 0 0 0 2 0 0 0 5 5 0\n 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 5 0\n 0 0 0 0 1 1 0 0 0 0]; 0 0 0 0 3 3 0 0 0 0\nThe largest pit in this image is Pit 1, with size 6.]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

You are given an N x M matrix of ones and zeros, which represents an image of a rectangular metal plate taken from the hull of a ship. Each element of the matrix denotes an area of the plate: The ones denote areas where the plate has corroded visibly, whereas zeros are areas where the metal is still in good condition. The corroded areas (the matrix elements with ones) can be found at multiple points on the metal plate.A collection of corroded areas that are next to each other is called a pit. Pits can come at different sizes, depending on how much they grew over the years. Pitting corrosion is important to quantify because it gives an idea of the reliability of the ship structure.For this problem, a pit is defined more clearly as follows: Two corroded areas at [row R1, column C1] and [row R2, column C2] belong to the same pit if and only if <tt>max(abs(R1-R2),abs(C1-C2)) &lt;= 1</tt>. In other words, if two corroded areas are adjacent horizontally, vertically, or diagonally, then both are considered to belong to the same pit.The size of a pit is equal to the number of corroded areas (or ones) that belong to it.Write a function that accepts a matrix X denoting the image in question. Output the size of the largest pit in this image. You are ensured that the size of the matrix is constrained at 1 &lt;= N &lt;= 20 and 1 &lt;= M &lt;= 20.As an example, consider the following 10 x 10 image (left). The corroded areas that belong to the same pit are then labeled, showing that the largest pit is Pit 1, with a size of 6 (right). In contrast, Pits 2, 3, 4 and 5 have size 2, 2, 4, and 4, respectively.<pre class="language-matlab">Sample test case:
X = [0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 4 4 0
 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 4 4 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 1 0 0 0 0 1 0 0 0 0 2 0 0 0 0 5 0 0
 0 0 0 1 0 0 0 1 1 0 0 0 0 2 0 0 0 5 5 0
 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 5 0
 0 0 0 0 1 1 0 0 0 0]; 0 0 0 0 3 3 0 0 0 0
The largest pit in this image is Pit 1, with size 6.
</pre>

You are given an N x M matrix of _ones_ and _zeros_, which represents an image of a rectangular metal plate taken from the hull of a ship. Each element of the matrix denotes an area of the plate: The _ones_ denote areas where the plate has corroded visibly, whereas _zeros_ are areas where the metal is still in good condition. The *corroded areas* (the matrix elements with _ones_) can be found at multiple points on the metal plate.

A collection of *corroded areas* that are next to each other is called a _pit_. Pits can come at different sizes, depending on how much they grew over the years. Pitting corrosion is important to quantify because it gives an idea of the reliability of the ship structure.

For this problem, a _pit_ is defined more clearly as follows: Two *corroded areas* at [row _R1_, column _C1_] and [row _R2_, column _C2_] belong _to the same pit_ if and only if |max(abs(R1-R2),abs(C1-C2)) <= 1|. In other words, if two *corroded areas* are adjacent horizontally, vertically, or diagonally, then both are considered to belong to the same pit.

The size of a pit is equal to the number of *corroded areas* (or _ones_) that belong to it.

Write a function that accepts a matrix X denoting the image in question. Output the size of the largest pit in this image. You are ensured that the size of the matrix is constrained at 1 <= N <= 20 and 1 <= M <= 20.

As an example, consider the following 10 x 10 image (left). The *corroded areas* that belong to the same pit are then labeled, showing that the largest pit is Pit 1, with a size of 6 (right). In contrast, Pits 2, 3, 4 and 5 have size 2, 2, 4, and 4, respectively.

Sample test case:
  X = [0 0 1 0 0 0 0 0 0 0        0 0 1 0 0 0 0 0 0 0
       0 1 1 0 0 0 0 0 0 0        0 1 1 0 0 0 0 0 0 0
       0 0 1 1 0 0 0 1 1 0        0 0 1 1 0 0 0 4 4 0
       0 0 0 1 0 0 0 1 1 0        0 0 0 1 0 0 0 4 4 0
       0 0 0 0 0 0 0 0 0 0        0 0 0 0 0 0 0 0 0 0
       0 0 0 0 0 0 0 0 0 0        0 0 0 0 0 0 0 0 0 0
       0 0 1 0 0 0 0 1 0 0        0 0 2 0 0 0 0 5 0 0
       0 0 0 1 0 0 0 1 1 0        0 0 0 2 0 0 0 5 5 0
       0 0 0 0 0 0 0 0 1 0        0 0 0 0 0 0 0 0 5 0
       0 0 0 0 1 1 0 0 0 0];      0 0 0 0 3 3 0 0 0 0
  The largest pit in this image is Pit 1, with size 6.

Solve

Solution Stats

152 Solutions
16 Solvers

Last Solution submitted on Nov 11, 2021

Last 200 Solutions

Problem Comments

Problem Recent Solvers16

Problem Tags

chemical engineering dfs flood fill

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45432. Pitting corrosion on a metal plate: Find the largest pit

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers16

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Problem 45432. Pitting corrosion on a metal plate: Find the largest pit

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers16

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Players