|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||1024 MB||19||7||7||70.000%|
Consider a black and white image, where every pixel has a value of either 0 or 1. Define a region of the image as a collection of pixels that all have the same value, and are interconnected. Specifically, for any two pixels in a region, there is a path between them only going up, down, left or right, and only going through other pixels with the same value.
You wish to see a border completely around every region in the image. You can choose certain regions to draw a border around; when you do, you draw a border around the entire region, including any internal “holes” (regions entirely contained within the region). If two regions are adjacent, then you can supply the border between then by drawing the border around one, or the other, or both. What is the minimum number of regions you need to draw a border around in order to ensure that every region has a border?
Consider these examples:
The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 100$), where $n$ is the number of rows in the image, and $m$ is the number of columns.
Each of the next $n$ lines contains a single string of length $m$, consisting only of the characters ‘
0’ and ‘
1’. This is the image.
Output a single integer, which is the minimum number of regions you must draw a border around to ensure that every region has a border.
3 3 000 111 000
3 3 000 010 000
3 3 010 101 010