Advertising Billboard
InterviewTime limit2sMemory limit512 MB
Given k on/off patterns for an n by m grid of bulbs, partition the bulbs into the fewest groups so that within each pattern every group is uniformly on or uniformly off.
- Level
Medium6 of 10
- Topics
- Union-find, Implementation, Hash map, Brute force
- Solved
- No attempts yet
Problem
To advertise its new products in China, a company decided to put an advertising billboard on a skyscraper. The billboard consists of light bulbs arranged in a rectangular grid of rows and columns. At any moment each bulb is either on or off.
The advertising message consists of characters, which are shown one after another. For each character, the bulbs that must be on while that character is displayed are known. The remaining bulbs must be off.
A special system is being developed to control the billboard. The system can turn bulbs on and off in whole groups. All bulbs are split into several groups so that, in each character, the bulbs of one group must be either all on or all off.
To optimize the operation of the control system, the bulbs must be split into the smallest possible number of such groups. Help the employees of the company's advertising department solve this problem.
Input
The first line of the input file contains the numbers , , and (), which are the number of characters in the advertising message, the height, and the width of the billboard.
Then lines describe the characters. Each of the characters is given by lines of characters each. All these lines consist only of the characters <<*>> and <<.>>, where <<*>> corresponds to a bulb that is on and <<.>> to a bulb that is off.
Output
Print the minimum number of groups into which the bulbs can be split.
Hint
In the given example, the bulbs can be split into groups as follows: the two bulbs in the first column form one group, the two bulbs in the last column form the second, and each of the two remaining bulbs forms a separate group.