Connection Status:
Competition Arena > SnakeCount

SnakeCount

SRM 284 · 2006-01-21 · by dgoodman

SRM 284 · 2006-01-21 · by dgoodman · Recursion
Class Name: SnakeCount
Return Type: int
Method Name: number
Arg Types: (vector<string>)
Problem Statement

Problem Statement

We are using aerial photography to estimate the number of snakes in a region. We have a rectangular image of pixels with values 0 or 1, and we want to count the number of snakes in the image. The 0's are background, and the 1's are snake-colored. Because of the attributes of this type of snake (not gregarious and not likely to curl up tightly), we have adopted the following rules for identifying a snake:
  • A snake is never adjacent to a snake-colored pixel that is not part of itself, not even diagonally.
  • There is a sequence of orthogonally adjacent pixels that traces out the entire snake from its head to its tail.
  • Two pixels of a snake cannot be orthogonally adjacent unless they are connected in the snake (i.e., are neighbors in the sequence that traces out the snake).
  • A snake occupies between 3 and 20 pixels, inclusive.
As an example, consider the following picture. There are several ways to trace an orthogonal connection from a head to a tail, but it is NOT a snake since whichever way you trace out the snake, there are pixels that are orthogonally adjacent to each other but which are not neighbors in the sequence that traced out the snake.

    11110
    01110

Create a class SnakeCount that contains a method number that is given a String[] image and that returns the number of snakes in the image.

Notes

  • A pixel is "orthogonally" adjacent to another if it is directly above, below, left or right of the other pixel.

Constraints

  • image will contain between 1 and 50 elements, inclusive.
  • Each element of image will contain exactly n characters, where n is between 1 and 50, inclusive.
  • Each character in each element of image will be '0' (zero) or '1' (one).
Examples
0)
{"11111111",
 "00000010",
 "11100000",
 "00010001",
 "10110011"}
Returns: 1

The possible snake at the top does not have a head to tail connection that includes all its pixels. The 2 possible snakes of length 3 in the middle of the image are eliminated because each is adjacent to a snake-colored pixel diagonally. The possible snake in the lower left corner is too short. There is a snake in the lower right corner.

1)
{"110111",
 "110101",
 "000110"}
Returns: 1

The four pixels in the upper left do not make a snake -- the head of a snake cannot be orthogonally adjacent to its tail. The 7 snake-colored pixels in the right 3 columns do make a legitimate snake.

2)
{"111","101","111"}
Returns: 0

This is not a snake since the head cannot be orthogonally adjacent to the tail.

3)
{"111","111","101"}
Returns: 0
4)
{"110000",
 "001111",
 "000000"}
Returns: 0
7)
{
"11111111111111111111111111111111111111111111111111",
"00000000000000000000000000000000000000000000000001",
"11111111111111111111111111111111111111111111111111"
}
Returns: 0

A snake can not occupy more than 20 pixels.

22)
{
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"10101010101010101010101010101010101010101010101010",
"00000000000000000000000000000000000000000000000000",
"11011011011011011011011011011011011011011011011011",
"10010010010010010010010010010010010010010010010001"
}
Returns: 317

A lot of snakes.

Submissions are judged against all 79 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SnakeCount with a public method int number(vector<string> image) · 79 test cases · 2 s / 256 MB per case

Submitting as anonymous