1058 : Longest
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
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
ความช่วยเหลือ: Hint[1] Hint[2]
เราต้องการวางลวดตัวนำายิ่งยวดลงบนแผ่นวงจรดังกล่าว โดยมีเงื่อนไขดังนี้
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]
กำลังออนไลน์: 24 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)