Indian National Olympiad in Informatics

Related:

Online Programming Contest, 14-15 January 2006

IARCS home > OLYMPIAD

Basic Division

Problem 1: Satellite Images, (K Narayan Kumar, CMI)

The Siruseri Weather Forecasting service receives images from its weather satellite every day. These images consist of a dark background on which there are white areas indicating cloud accumulation. The SWF service has a rather simplified model for storms - it has decided any white area exceeding a certain size must be a storm. For our purposes the satellite image is represented by a grid of #'s and .'s. A # denotes a cloud free area while a . indicates the presence of a cloud. Each point on the grid has upto 8 neighbours (north-east, north, north-west, east, west, south-east, south and south-west) and a cloud consists of a contiguous collection of .'s.

For example, in the following image, there are 4 patches of cloud.

#####.#####
####.####.#
###..##.#.#
##...######
######.....
###########

If the threshold for the identification of a storm is 4 units then there are only 2 storms, marked by 1 and 2 below:

#####1#####
####1####.#
###11##.#.#
##111######
######22222
###########

You will be given the satellite map and the threshold. Your task is the determine the number of storms as well as the size of the largest storm.

Input format

The first line of the input contains two integers M and N indicating the number of rows and columns in the satellite image. This is followed by M lines describing the satellite image. Line M+2 contains a single positive integer K indicating the threshold that determines a storm.

Output format

Two space separated integers n and s in a single line indicating the number of storms and the size of the largest storm respectively.

Test data

You may assume that 1 ≤ M,N ≤ 60 in 80% of the inputs. In all the inputs 1 ≤ M,N ≤ 1000.

Example

We now illustrate the input and output formats using the example described above.

Sample input

6 11
#####.#####
####.####.#
###..##.#.#
##...######
######.....
###########
4

Sample output

2 7