1044.html

<span style="font-family: Courier New;">คณะกรรมการผู้บริหารเมืองแห่งหนึ่งต้องการทำการตัดถนนผ่านพื้นที่ใจกลางเมือง โดยความต้องการของเมืองคือการตัดถนนเป็นเส้นตรงผ่านเมืองเป็นเส้นตรงทางทิศทางใดก็ได้ ระหว่างการตัดถนนผ่านทางด้านทิศตะวันตกไปยังด้านทิศตะวันออก (ซ้ายไปขวา) หรือทางด้านทิศเหนือไปยังด้านทิศใต้ (บนลงล่าง) ซึ่งพื้นที่ดังกล่าวมีมูลค่าของพื้นที่ในแต่ละส่วนไม่เท่ากัน&nbsp; นอกเหนือจากนั้นเมื่อตัดถนนแล้วจะทำให้พื้นที่ที่อยู่ติดถนนมีมูลค่าสูงขึ้น เพื่อให้การตัดถนนทำให้เกิดความเสียหายน้อยที่สุดและเพื่อประโยชน์ของเมืองโดยรวม การตัดถนนจึงควรตัดผ่านพื้นที่ที่มีมูลค่าต่ำที่สุดและยังทำให้มูลค่าพื้นที่โดยรวมของเมืองมีมูลค่าเพิ่มขึ้นสูงสุดอีกด้วย <br />
<u><strong><br />
โจทย์</strong></u><br />
จงเขียนโปรแกรมเพื่ออ่านข้อมูลนำเข้าของมูลค่าพื้นที่ย่อยภายในเมือง และการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีการตัดถนนผ่าน ทั้งนี้กำหนดให้พื้นที่ภายในเมืองมีรูปทรงเป็นสี่เหลี่ยมผืนผ้าหรือสี่เหลี่ยมจัตุรัสเสมอ จากนั้นให้คำนวณหาเส้นทางที่ทำให้มูลค่าพื้นที่ของเมืองโดยรวมมีมูลค่าสูงที่สุดเพื่อให้คณะกรรมการนำไปพิจารณาทำการตัดถนน โดยกำหนดให้เส้นทางที่ถูกทำเป็นถนนจะมีมูลค่าพื้นที่เหลือ 0<br />
<center><br />
<img align="middle" src="./img/1044/1044-1.gif" alt="" /><br />
</center><br />
<u><strong>ข้อมูลนำเข้า</strong></u><br />
<strong>บรรทัดแรกของข้อมูลนำเข้า</strong>เป็นจำนวนเต็มสองตัว n (2 &lt; n &lt;= 100) และ m (2 &lt; m &lt;= 100) ซึ่งเป็นขนาดของพื้นที่เมือง <br />
<strong>ใน n บรรทัดถัดไป </strong>(เริ่มจากบรรทัดที่ 2 ถึงบรรทัดที่ n+1) เป็นข้อมูลของมูลค่าพื้นที่ย่อยจากเหนือลงใต้ โดยบรรทัดที่ i+1 จะแสดงข้อมูลของพื้นที่ย่อยในแถวที่ i (1 &lt;= i &lt;= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 100<br />
<strong>ใน n บรรทัดถัดไป </strong>(เริ่มจากบรรทัดที่ n+2) เป็นข้อมูลการเปลี่ยนแปลงมูลค่าของพื้นที่ย่อยเมื่อมีถนนตัดผ่าน โดยบรรทัดที่ n+i+1 จะแสดงข้อมูลของการเปลี่ยนแปลงมูลค่าพื้นที่ย่อยในแถวที่ i (1 &lt;= i &lt;= n) โดยที่แต่ละบรรทัดจะมีตัวเลขทั้งหมด m ตัว (ตัวเลขแต่ละตัวจะถูกคั่นด้วยช่องว่าง) โดยตัวเลขแต่ละตัวในแต่ละบรรทัดเป็นจำนวนเต็มมีค่าระหว่าง 0 ถึง 20 (ซึ่งอาจจะทำให้มูลค่าของพื้นที่ย่อยมีค่าเกิน 100 ได้)<br />
<br />
<u><strong>ข้อมูลส่งออก</strong></u><br />
มีทั้งหมด 1 บรรทัด มีตัวเลข 1 ตัวซึ่งแสดงถึงมูลค่ารวมของพื้นที่ภายในเมืองหลังจากทำการตัดถนนเรียบร้อยแล้ว<br />
<br />
<u><strong>ที่มา</strong></u><strong>: </strong><b>การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2550 </b></span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>5 4
<br />2 3 2 1
<br />4 5 8 4
<br />2 5 3 2
<br />1 4 0 2
<br />2 1 8 1
<br />1 2 3 2
<br />2 2 2 1
<br />2 1 1 2
<br />1 2 1 0
<br />1 1 1 0</td>
				<td>62</td>
			</tr></table>