1152 : ไฟ (Fire)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

                บ้านของคุณมีลักษณะเป็นกริดสี่เหลี่ยมขนาด N*N ในแต่ละช่องของกริดนั้น คุณได้เก็บของสำคัญของคุณแต่ละชิ้นไว้ในแต่ละช่อง โดยที่ช่อง (i,j) จะมีของมูลค่า Vi,j ของคุณเก็บอยู่

                วันหนึ่ง ได้เกิดเหตุการณ์ไฟไหม้วินาศกรรมครั้งยิ่งใหญ่ขึ้นที่บ้านของคุณ ไฟนั้นจะเริ่มที่พิกัด (1,1) ซึ่งก็คือช่องซ้ายบนของบ้าน และไฟจะลามไปเรื่อยๆอย่างไม่มีที่สิ้นสุด !

                ลักษณะการลุกลามของไฟจะความเฉพาะตัวคือ “ทุกๆ 1 นาที ช่องที่ติดกับช่องที่มีไฟอยู่ ไม่ว่าจะติดทางซ้าย ขวา บน ล่าง จะติดไฟด้วย (ไม่นับแนวทแยง)”

                คุณต้องการจะปกป้องทรัพย์สมบัติของคุณไว้ให้ได้มากที่สุด ซึ่งทุกๆ 1 นาที คุณจะสามารถอพยพของของคุณออกไปจากบ้านได้ 1 ชิ้น (สังเกตได้ว่าสมบติที่ช่อง (1,1) ไม่สามารถอพยพออกไปได้ทันอย่างแน่นอน)

                จงเขียนโปรแกรมหาว่าจะสามารถอพยพของออกไปจากบ้านได้มูลค่ารวมมากที่สุดเท่าไร

 

                ข้อมูลนำเข้า

บรรรทัดแรก : จำนวนนับ N แทนขนาดบ้านของคุณ ( 1 < N < 1000 )
บรรทัดถัดไป N บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนนับ N จำนวน โดยตัวเลขบรรทัดที่ i ลำดับที่ j จะแทนค่า Vi,j ( 1 < Vi,j < 10 000 )

               

                ข้อมูลส่งออก

บรรทัดแรกและบรรทัดเดียว แสดงมูลค่ารวมของสมบัติที่คุณอพยพออกจากบ้านได้ทัน


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5
50 36 10 13 2 
17 5 16 42 41 
49 12 38 9 25 
18 4 36 31 11 
30 6 3 46 50 
333
5
30 46 17 43 35 
31 24 7 8 49 
42 11 11 3 31 
32 10 42 35 35 
27 3 29 47 43 
347

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)