320. The Influence of the Mafia

Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

The problem with zones of influence was finally solved during the recent Berland mafia meeting. Berland was represented as a rectangle of N x M squares. All squares were divided between the mafia leaders. Each leader got a connected region of squares, i.e. it is possible to get from any square of the region to any other by making moves only across the squares of this region. Four types of moves are allowed: up, down, left and right.

Each leader was assigned a number from 0 to 9, it is allowed for two different leaders to have the same number. The leaders decided to create a map of Berland where each square has the number of the leader who owes it. The secretary was able to assign leaders with numbers in such a way that no two bordering regions on the map have the same number. The valiant Berland police seized the map with the numbers. And now the chief of the police wants to know the degree of the mafia influence in Berland.

He introduced following definitions:

  • A leader is called big if he possesses K or more squares.

  • A square is called dangerous if it is controlled by a big leader or if there exists such big leader that it is impossible to get out of Berland (i.e. to get to a square on the border of the country) without visiting a square controlled by this leader. Allowed moves: up, down, left and right.

    The chief of the police wants to know the number of dangerous squares in the country. He decided to ask his valiant programmers to solve this important task.

    The first line of the input contains integer numbers N, M and K (1≤ N, M≤ 500; 1≤ K≤ 250000). The map created by the secretary follows. The map is written in the form of N lines with M numbers from 0 to 9 in each line. Numbers in a line are written one after another without spaces.

    Write to the output the number of dangerous squares in the country.

    sample input
    sample output
    7 6 4

    There are two big leaders in the country (both are marked with the number 1, one has 4 squares, another has 9 squares). There is one more dangerous square (marked with the number 9) besides the regions in possession of big leaders. Note that squares marked with the number 8 are not dangerous, as they do not satisfy the definition of a dangerous square.

  • Online Contester Team © 2002 - 2010. All rights reserved.