JDCC '17 Contest 1 S4 - A Ghost Oddity

View as PDF

Submit solution

Points: 10
Time limit: 2.0s
Memory limit: 256M

Problem type

After all the trick or treaters have left, Vlad goes outside to take pictures of his decorated home. In order to make sure he got a good shot, he decides to take two pictures back to back.

When he comes back inside and looks at his pictures, he sees a few inconsistencies between the first and second image. Vlad realises that these inconsistencies must be ghosts that scattered after seeing his flash. Vlad knows that his discovery will shake the world, however before he publishes his finding he must first know how many ghosts he managed to photograph.

Vlad assumes that any two adjacent pixels (vertical/horizontal/diagonal) that are both inconsistent across the two images must belong to the same ghost. He also assumes there will always be empty space between two ghosts (ghosts stay away from each other as they fear passing through each other). Can you help Vlad figure out how many ghosts were in the first picture?

Input Specification

The first line of input contains two integers R, C \((1 \le R, ​C ​\le 500)\), the number of rows and columns in his image. The next R ​lines each contain C characters, describing the first image. After the first image is a blank line followed by another R​ ​lines with C characters each, describing the second image. The image consists of the characters . and #.

Output Specification

Output a single integer, the number of ghosts in the image.

Sample​ ​Input​ ​1

3 5
#####
#####
#####
#####
#.#.#
#####

Sample​ ​Output​ ​1

2

Sample​ ​Input​ ​2

7 9
#...#..#.
.###.##.#
.#....#..
.####.##.
.#..##.#.
.#.....#.
.#..#..#.
....#....
...#.#...
..#...#..
.#######.
.#.....#.
.#..#..#.
.#..#..#.

Sample Output 2

3

Comments

There are no comments at the moment.