DMPG '18 S3 - Black and White IV

View as PDF

Submit solution

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 M by N 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 M by N 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 M by N 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.

Constraints

Subtask 1 [20%]

1 \le M, N \le 70

Subtask 2 [30%]

1 \le M, N \le 400

Subtask 3 [50%]

1 \le M, N \le 2\,000

Input Specification

The first line will contain two space-separated integers, M and N in that order.
The next M lines will each contain a single string of length N. 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

Comments

There are no comments at the moment.