Internet Problem Solving Contest

IPSC 2012

Problem A – Abundance of sweets

Georg has a new profession: he now works in a candy factory. The job is way more boring than it sounds: he is responsible for quality assurance. And that means taking a box of candies, counting them and checking that none are missing. Help poor Georg! Write a program that will do the job for him.

You will be given a matrix with r rows and c columns. This matrix represents the top view of a box of candies. The matrix will only contain the following characters:

There are exactly two ways how a whole piece of candy looks like:
         1. >o<    2. v

Whenever you see three characters arranged in this way, you see a whole piece of candy.

Problem specification

For the given matrix count the number of whole pieces of candy it contains.

In the easy data set the box will only contain whole pieces of candy and nothing else.

In the hard data set the box can also contain fragment of candies: characters o<>v^ that don’t belong to any whole candy. To make your life easier, you may assume that the following configuration will never appear in the hard data set:

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

The first line of each test case contains two integers r and c (1 r,c 400): the dimensions of the matrix. Each of the next r lines contains one row of the matrix: c characters from the set “.o<>v^”. (Their ASCII values are 46, 111, 60, 62, 118, and 94.)

Output specification

For each test case, output a single line with one integer – the number of whole candies in the box.



5 4

There are three whole candies: in the first row, in the last row, and in the first column.