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


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

ห้องที่มหาวิทยาลัยขอนแก่นได้มีการปูพื้นกระเบื้องใหม่ในช่วงของการแข่งขันคอมพิวเตอร์โอลิมปิก สอวน โดยเฉพาะ ห้องมีหลายขนาดโดยทุกห้องจะเป็นสี่เหลี่ยมจัตุรัสที่มีขนาด n x n โดย n เป็นจำนวนเต็ม (2 ≤ n ≤ 17) ซึ่งทุกห้องจะมีมุมห้องด้านบนขวาที่จะไม่ปูกระเบื้อง ทั้งนี้กระเบื้องหนึ่งแผ่นมีขนาด 1x1 หน่วย

ตัวอย่างเช่น ถ้า n มีขนาดเท่ากับ 2, 3 และ 4 ตามลำดับ จะได้การวางกระเบื้องตามลำดับดังแสดงในภาพที่ ๑ โดยสีขาวจะเป็นตำแหน่งของกระเบื้อง ส่วนสีดำเป็นส่วนช่องว่างที่ไม่ได้ปู



อย่างไรก็ตามนอกจากรูปห้องจะประหลาดแล้ว กระเบื้องที่สั่งซื้อมาก็ยังประหลาดอีก โดยกระเบื้องจะถูกนำมาติดกันเป็น “ผืน” โดยหนึ่งผืนจะมีเพียงสี่แบบซึ่งเป็นการนำกระเบื้องสามแผ่นมาวางติดกัน ดังภาพที่ ๒ แม้ว่าเมื่อหมุนแล้วจะดูหน้าตาเหมือนกัน แต่ช่างปูกระเบื้องก็เป็นคนประหลาดอีกที่ไม่ยอมหมุนกระเบื้อง ทำให้ลักษณะของผืนกระเบื้องจะมีลักษณะดังที่เห็นในภาพ



ตัวอย่าง ภาพที่ ๓ แสดงตัวอย่างของการปูผืนกระเบื้อง กระเบื้องทุกแผ่นจะมีหมายเลขเป็นจำนวนเต็มกำกับ แต่ละแผ่นอาจมีหมายเลขที่ซ้ำกันได้ กระเบื้องที่มีหมายเลขเดียวกันและอยู่ติดกันจะถือว่าอยู่บน “ผืน” เดียวกัน



ภาพที่ ๔ แสดงการปูกระเบื้องที่ใช้ผืนกระเบื้องที่ถูกต้อง (ผืนหมายเลข 1) อยู่หนึ่งผืนปะปนอยู่กับผืนกระเบื้องที่ไม่ถูกต้อง (ผืนหมายเลข 2 และ 3)



คำสั่ง
จงเขียนโปรแกรมเพื่อนับจำนวนผืนกระเบื้องที่มีลักษณะถูกต้อง

ข้อมูลนำเข้า
บรรทัดแรก เป็นเลขจำนวนเต็มบวก n ซึ่งบอกขนาดของห้อง
ต่อจากนั้น n บรรทัด แสดงรายละเอียดการปูกระเบื้องขนาด n x n โดยแต่ละบรรทัดประกอบด้วยจำนวนเต็ม n ค่าคั่นด้วยช่องว่างหนึ่งช่อง ซึ่งจำนวนเต็ม k (1 ≤ k ≤ 9) แต่ละตัวคือหมายเลขของกระเบื้อง ทั้งนี้จำนวนเต็ม 0 แทนมุมห้องที่ไม่ได้ปูกระเบื้อง

ข้อมูลส่งออก
มีจำนวนเต็มค่าเดียว ซึ่งแทนจำนวนผืนกระเบื้องที่ถูกต้อง

ที่มา: การแข่งขันคอมพิวเตอร์โอลิมปิก สอวน. ครั้งที่ 3 มหาวิทยาลัยขอนแก่น

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
3
1 1 0
1 2 2
3 2 2 		1
5
3 3 6 6 0
3 5 5 6 8
2 2 5 8 8
2 1 4 4 7
1 1 4 7 7 		8

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