Gcj2009
ไปยังการนำทาง
ไปยังการค้นหา
Round 2
A. Crazy Rows
Source: [1]
คุณได้รับเมตริกซ์ขนาด N x N ที่มีค่า 0 กับ 1 คุณสามารถสลับสองแถวที่ติดกันในเมตริกซ์ได้
เป้าหมายของคุณคือการสลับให้ค่า 1 ทั้งหมดอยู่บนหรือล่างแนวทแยงมุมหลัก นั่นคือ สำหรับ X ที่ 1 <= X <= N, จะต้องไม่มี 1 ในแถวที่ X ที่อยู่ด้านขวาของคอลัมน์ X
ให้โปรแกรมพิมพ์จำนวนครั้งของการสลับที่น้อยที่สุดที่ต้องใช้
Input
- บรรทัดแรกระบุจำนวนเต็ม T, จากนั้นจะมีข้อมูลทดสอบ T ชุดหลังจากนั้น
- บรรทัดแรกของแต่ละชุดข้อมูลทดสอบระบุจำนวนเต็ม N จากนั้นอีก N บรรทัด ในแต่ละบรรทัดจะมีอักขระ N ตัว ซึ่งมีค่าเป็น 0 หรือ 1
Output
สำหรับแต่ละข้อมูลทดสอบ พิมพ์
Case #X: K
เมื่อ X แทนหมายเลขข้อมูลทดสอบ และ K เป็นจำนวนครั้งที่ต้องสลับที่น้อยที่สุด
รับประกันว่ามีคำตอบในทุก ๆ ข้อมูลทดสอบ