จุดเทียนภาวนา (toi11_candle)


Time limit:
1000 ms
Memory limit:
48 MB

เมื่อครั้งรายาบุหลันผู้ครองบุหงาตันหยงนครมายาวนานสิ้นพระชนม์ ชาวเมืองต้างเศร้าโศกอาลัยเป็นอย่างมากทุกคนต่างรวมตัวกันที่ลานพิธีกรรมเพื่อจุดเทียนและสวดภาวนาตามธรรมเนียมที่ปฏิบัติกันมาเพื่อแสดงความอาลัยและส่งดวงพระวิญญาณสู่สวรรคาลัย

ลานพิธีกรรมถูกปูด้วยกระเบื้องสี่เหลี่ยมจัตุรัสยาวด้านละ 1 หน่วย โดยปูกระเบื้องชิดกัน M แถวและ N หลัก ผู้มาร่วมไว้อาลัยและสวดภาวนาจะเลือกนั่งบนกระเบื้องตามอัธยาศัย แต่ต้องนั่งหนึ่งคนต่อกระเบื้องหนึ่งแผ่น เมื่อเลือกที่นั่งได้แล้วทุกคนจะไม่ลุกจากที่นั่ง จนกว่าจะเสร็จสิ้นการสวดภาวนา

ก่อนสวดภาวนา ทุกคนจะต้องจุดเทียนด้วยไม้ขีด หรือหากไม่มีไม้ขีดจะต้องรอต่อไฟเทียนจากผู้ที่นั่งติดกันคนใดคนหนึ่งจากทั้ง 8 ทิศทาง และไม่สามารถลุกจากกระเบื้องเพื่อไปต่อเทียนจากคนอื่นที่ไม่ได้นั่งบนกระเบื้องแผ่นที่อยู่ติดกัน พิธีการสวดภาวนาจะรอจนกระทั่งทุกคนที่มาร่วมพิธีจุดเทียนเรียบร้อยแล้ว ประธานในพิธีจึงจะเริ่มนําสวดภาวนาอย่างพร้อมเพรียงกัน ด้วยความเป็นผู้ประหยัดมัธยัสถ์ตามวิถีปฏิบัติของคนในบุหงาตันหยงนคร แม้ในยามที่เป็นพิธีอาลัยผู้ครองนครอันยิ่งใหญ่ ชาวเมืองที่มาร้วมงานก็พยายามที่ใช้จํานวนไม้ขีดไฟให้น้อยที่สุดที่เป็นไปได้ ดังตัวอย่างในรูปที่ 1

รูปที่ 1 ตัวอย่างการจุดเทียนในการสวดภาวนาโดยใช้ไม้ขีดไฟน้อยที่สุดเพียง 3 ก้าน
(เป็นรูปแบบหนึ่งจากหลายรูปแบบที่เป็นไปได้)
 

จงเขียนโปรแกรมเพื่อหาจํานวนไม้ขีดไฟที่น้อยที่สุด ซึ่งทําให้ทุกคนจุดเทียนได้และพร้อมที่จะสวดภาวนา

Input

บรรทัดแรก มีจํานวนเต็มสองจํานวน คือ M ระบุจํานวนแถวและ N ระบุจํานวนหลักของลานพิธีกรรม แต่ละจํานวนถูกคั่นด้วยช่องว่างหนึ่งช่อง กําหนดให้ 2 ≤ M, N ≤ 2,000

บรรทัดที่ 2 ถึง M+1 แต่ละบรรทัดประกอบด้วยสตริงขนาด N ตัวอักขระ แต่ละอักขระแสดงการนั่งของผู้เข้าร่วมสวดภาวนาในพิธี โดยกําหนดให้ ‘0’ แทนพื้นที่ว่างที่ไม่มีคนนั่ง และ  ‘1’ แทนพื้นที่ที่มีคนนั่ง

Output

มีหนึ่งบรรทัด ระบุจํานวนไม้ขีดไฟที่น้อยที่สุด ซึ่งทําให้ทุกคนจุดเทียนได้และพร้อมที่จะสวดภาวนา

Constrains/Subtasks

อย่างน้อย 20% ของข้อมูลทดสอบ M, N ≤ 20

อย่างน้อย 60% ของข้อมูลทดสอบ M, N ≤ 300

Editor:

Source: Thailand Olympiad in Informatics 2015 (TOI11 / TOI 2015)

Select description language

Thai (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None