Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Snakes on a Plane
Description Assume we have an n × m grid of squares, each filled with either 0 or 1. A - Each snake square has a 1 in it
- Each snake square touches exactly two other snake squares (north/south/east/west), except the first and last square in the sequence (the head and tail of the snake)
maximal snake is one in which we cannot add a 1 to either end without either lengthening the snake, combining two snakes together, or violating rule 2 above. The examples below show grids with and without maximal snakes (all empty squares have 0's in them). Notice that the second grid does not have a maximal snake since you can add a 1 at the end of either snake to get a larger snake.For this problem, you will be given grids and must count the number of maximal snakes in each. Input Input will consist of multiple test cases. The first line of each test case will contain two positive integers Output For each test case, output a single line containing the number of maximal snakes in the grid. Sample Input 7 10 1111111110 0000000010 1100000011 1011110001 1010010001 1010010111 1110011100 7 10 1111111110 0000000010 0001010011 1011010001 1010010001 1010010111 1110011100 7 10 1011111110 0100000010 1101011011 1011010001 1010010001 1010010111 1110011100 0 0 Sample Output 1 0 3 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator