Finding Snakes
Time limit2sMemory limit128 MB
Count connected 1-shapes in a grid that form a simple path (snake) with no possible one-cell extension at either end.
- Level
Medium6 of 10
- Topics
- Graph, DFS, Implementation
- Solved
- No attempts yet
Problem
An n x m grid is filled with 0s and 1s. Cells containing 1 may be connected through their four cardinal neighbors to form a shape.
A snake is one connected group of 1-cells. In that group, every cell except the two ends must be adjacent, through the four cardinal directions, to exactly two cells from the same group. An end cell is where the snake starts or finishes, and a group with only one cell is treated as a snake of length 1.
A snake is not maximal if it can be made longer from any end. More precisely, if a 0-cell adjacent to an end can be changed to 1 and that new cell touches only that end, then the snake can simply be extended by one cell and is not maximal. A snake is maximal when no such extension is possible from any end.
Given the grid, count the maximal snakes.
Input
The first line contains two integers n and m (1 <= n, m <= 200).
Each of the next n lines contains the grid information as a string of length m consisting only of 0 and 1.
Output
Print the number of maximal snakes.