ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Internal Contest March'2003

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. Ancient Necropolis

Time limit: 2.5 second
Memory limit: 4 MB
Aerophotography data provide a bitmap picture of a hard-to-reach region. According to the suggestions of scientists, this region is a cemetery of an extinct civilization. Indeed, the picture, having been converted to a binary form, shows distinctly visible areas, dark (marked with symbols 1) and light (marked with 0). It seems that the dark areas are tombstones. It's easy to either confirm or reject the hypothesis since the race that lived in the region knew astronomy, so tombstones were always oriented along the Earth's parallels and meridians. That is why the dark areas in the picture should have the form of rectangles with the sides parallel to the axes. If it is so, then we indeed have a picture of a cemetery of an extinct race. Otherwise, new hypotheses should be suggested.


The first input line contains two integers N and M, which are the dimensions of the picture provided by the aerophotography. Each of the next N lines contains M zeros or ones separated with a space. The numbers N and М do not exceed 3000.


Output "Yes" if all connected dark areas in the picture are rectangles and "No" otherwise.


2 2
0 1
1 1
3 3
0 0 1
1 1 0
1 1 0
Problem Author: Nikita Shamgunov and Leonid Volkov
Problem Source: Open collegiate programming contest for student teams, Ural State University, March 15, 2003
To submit the solution for this problem go to the Problem set: 1249. Ancient Necropolis