Border
InterviewTime limit2sMemory limit256 MB
Given a grid of cells labeled A or B, count the unit edges that separate an A cell from a B cell.
- Level
Easy3 of 10
- Topics
- Array, Implementation, Simulation, Matrix
- Solved
- No attempts yet
Problem
In international politics, the border between states is an important concept. An unclear understanding by the parties of where the border runs can lead to international conflicts and even wars.
In this problem the situation is somewhat simpler, since the two states considered here have a clear understanding of which territory belongs to which of them.
The territory occupied by these two states is a rectangle h by w kilometers, divided into squares one kilometer on a side. Each of these squares belongs entirely to either the first state or the second.
You must determine the length of the border between the two states. A side of a unit square counts as part of the border if a square belonging to the first state lies on one side of it and a square belonging to the second lies on the other.
Input
The first line contains two integers: w and h, the dimensions of the rectangle in kilometers (1 ≤ w, h ≤ 100). The next h lines describe the territory. Each contains w characters. If a character is A, the corresponding unit square belongs to the first state, and if it is B, to the second. Each state is guaranteed to own at least one square.
The territory of each state is a connected region.
Output
Print a single integer: the length of the border between the states in kilometers.