Gcj2013/lawnmower

ต้นฉบับ (ทดลองส่งได้ที่เว็บต้นทาง): [1]

Problem

Alice และ Bob มีสนามหญ้าที่หน้าบ้านที่มีรูปร่างเป็นสี่เหลี่ยมขนาด N เมตร คูณ M เมตร ในแต่ละปี พวกเขาพยายามจะตัดหญ้าให้เป็นรูปแบบต่าง ๆ พวกเขาเคยใช้ที่ตัดหญ้าในการตัด แต่นั่นก็เป็นกิจกรรมที่เสียเวลามาก ตอนนี้พวกเขาเพิ่งได้เครื่องตัดหญ้าอัตโนมัติที่สามารถปรับค่าได้หลากหลาย ทำให้อยากจะลองเริ่มใช้เสียหน่อย

เครื่องตัดหญ้าใหม่นี้ สามารถปรับระดับความสูงในการตัดได้ โดยการปรับค่านั้นสามารถปรับค่าความสูง h ระหว่าง 1 ถึง 100 มิลลิเมตร เมื่อตั้งค่านี้แล้ว เครื่องจะตัดหญ้าที่มีความสูงมากกว่า h ให้เหลือความสูงเท่ากับ h    ในการตัดหญ้านั้นจะเริ่มตัดจากขอบด้านหนึ่ง จากนั้นเครื่องตัดหญ้าจะตัดหญ้าไปในทิศทางตรง ตั้งฉากกับขอบของสนามด้านที่เครื่องตัดหญ้าเริ่มเข้าไป โดยจะตัดเป็นแถบความกว้าง 1 เมตรพอดี จนกระทั่งเครื่องตัดไปทะลุขอบอีกด้านของสนาม    เครื่องตัดหญ้าสามารถปรับความสูงได้เฉพาะตอนที่ไม่ได้อยู่ในสนามเท่านั้น

Alice and Bob have a number of various patterns of grass that they could have on their lawn. For each of those, they want to know whether it's possible to cut the grass into this pattern with their new lawnmower. Each pattern is described by specifying the height of the grass on each 1m x 1m square of the lawn.

The grass is initially 100mm high on the whole lawn.