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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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.