DMPG '18 S3 - Black and White IV

View as PDF

Points: 7 (partial)
Time limit: 0.3s
Java 1.0s
Python 1.0s
Memory limit: 64M
Python 256M

Author:
Problem type

A particularly interesting math problem catches your eye! The problem is asking about an by grid. Some of these squares are coloured black while the rest are white. The grid in this problem is coloured in such a way that no four distinct black squares form a rectangle with sides parallel to the sides of the grid.

You are trying to see what kind of colourings of the by grid have this property. As such, you have given yourself a colouring of the grid. However, you aren't sure if the way you coloured it actually works.

Given a colouring of an by grid, determine whether or not there exist four distinct black squares which form a rectangle with sides parallel to the sides of the grid.

Clarification: These four distinct black squares must be exactly the four corners of the rectangle they form.

Input Specification

The first line will contain two space-separated integers, and in that order.
The next lines will each contain a single string of length . Each character will either be a . representing a white tile, or a # representing a black tile.

Output Specification

Output the answer on a single line. This answer should be yes if this colouring does not have a rectangle formed by four black squares. Otherwise, output no.

Sample Input 1

3 4
#.##
##..
..##

Sample Output 1

no

Sample Input 2

1 4
####

Sample Output 2

yes