[ ลืมรหัสผ่าน | ลงทะเบียนสมาชิกใหม่ ]    
  


1058 : Longest
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
สถิติโจทย์ข้อนี้ : ใช้เวลาน้อยที่สุด ทั้งหมด

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

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

รูปด้านล่างแสดงตัวอย่างการวางลวดตัวนำบนแผ่นวงจรขนาด 4 x 5 (ช่องสีขาวแทนช่องที่มีโลหะพิเศษ ช่องดำคือช่องธรรมดา)



เราต้องการทราบความยาวที่มากที่สุดของลวดตัวนำที่สามารถวางลงไปบนแผนวงจรได้

งานของคุณ
ให้เขียนโปรแกรมรับจำานวนแผ่นวงจร จากนั้น สำหรับแต่ละแผ่นวงจรก ให้เขียนโปรแกรมรับข้อมูลของการเคลือบแต่ละช่องของแผ่นวงจรนั้นแล้วคำานวณหาความยาวที่มากที่สุดของลวดตัวนำที่สามารถวางลงไปบนแผนวงจรได้

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม K แทนจำนวนแผ่นวงจรที่มี (1<=K<=5) จากนั้น ข้อมูลนำเข้าจะประกอบด้วยข้อมูล K ชุด แผ่นละหนึ่ง ชุด
สำาหรับแต่ละชุด บรรทัดแรกระบุจำนวนเต็ม M และ N (1 <= M <= 1,000; 1 <= N <= 1,000) จากนั้น อีก M บรรทัดของชุดนั้น จะระบุข้อมูลของแผ่นวงจร โดยในบรรทัดที่ 1 + i สำหรับ 1 <= i <= M จะมีสตริง Ai ความยาว N ตัวอักษร ระบุข้อมูลของแผ่นวงจรในแถวที่ i ตัวอักษรตัวที่ j ใน Ai จะมีค่าเป็น 1 ถ้าช่องที่ j เป็นช่องที่เคลือบโลหะพิเศษ และเป็น 0 ถ้าช่องที่ j เป็นช่องธรรมดา

ข้อมูลส่งออก
ข้อมูลส่งออกมี K บรรทัด แต่ละบรรทัดระบุจำานวนเต็มแทนความยาวของลวดตัวนำาที่มากที่สุด สำหรับข้อมูลของแผ่นวงจรแต่ละชุด

ขอบเขตเพิ่มเติม
ในข้อมูลชุดทดสอบที่มีคะแนนรวมไม่น้อยกว่า 70% ค่า K<=2, N <= 500, M <= 500

ที่มา: Young Thai Online Programming Competition 2008

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
2
4 5
11110
11011
01111
11110
2 5
01110
11000 		7
4

ความช่วยเหลือ: Hint[1]  Hint[2]