เกมการเชื่อมโยงตัวเลขใน C / C ++?

เกม - สมมติว่าอาร์เรย์ n × n ของสี่เหลี่ยม จากจำนวนนี้ สี่เหลี่ยมจัตุรัสบางอันว่างเปล่า บางอันเป็นรูปทึบ และสี่เหลี่ยมจัตุรัสที่ไม่ทึบบางอันถูกกำหนดโดยจำนวนเต็ม 1, 2, 3, … จำนวนเต็มแต่ละจำนวนจะคงไว้หรือใช้พื้นที่สองช่องที่ต่างกันบนกระดาน หน้าที่ของผู้เล่นคือการเชื่อมต่อทั้งสองเหตุการณ์ของจำนวนเต็มแต่ละจำนวนบนกระดานโดยใช้เส้นทางง่ายๆ ที่ใช้การเคลื่อนที่ในแนวนอนและแนวตั้งเพียงอย่างเดียว ไม่อนุญาตให้มีเส้นทางที่แตกต่างกันสองทางมาบรรจบกัน ไม่มีเส้นทางใดที่อาจรวมถึงสี่เหลี่ยมทึบ (ไม่อนุญาตให้ปรากฏสี่เหลี่ยมทึบบนเส้นทางใด ๆ ) ในที่สุด ช่องสี่เหลี่ยมที่ไม่ใช่ของแข็งทั้งหมดจะต้องถูกเติมด้วยเส้นทาง

อัลกอริทึม - ในการสร้างปริศนาสุ่มที่ถูกต้องด้วยขนาดกระดานที่กำหนด n × n ก่อนอื่นเราจะสร้างเส้นทางที่ไม่ตัดกันอย่างง่ายแบบสุ่มบนกระดาน หากสี่เหลี่ยมแยกบางส่วนยังคงอยู่นอกเส้นทางที่สร้างขึ้นทั้งหมด ให้ทำเครื่องหมายสี่เหลี่ยมแยกเหล่านี้เป็นทึบ (ต้องห้าม) ต่อไปเราจะระบุจุดสิ้นสุดของเส้นทางและรายการสี่เหลี่ยมทึบเป็นปริศนา

ดังนั้นเราจึงสร้างวิธีแก้ปัญหาขึ้นมาก่อน แล้วจึงไขปริศนาจากวิธีแก้ปัญหาต่อไป เส้นทางและสี่เหลี่ยมทึบแบ่งหรือแบ่งพาร์ติชันกระดาน n × n เราใช้โครงสร้างข้อมูล union-find เพื่อสร้างพาร์ติชันนี้ โครงสร้างข้อมูลจัดการกับชุดย่อยของชุดสี่เหลี่ยม n^2 บนกระดาน

PseudoCode

• ค้นหาช่องสี่เหลี่ยม (a, b) และ (c, d) แบบสุ่มบนกระดานเพื่อให้ -

  • (a, b) และ (c, d) เป็นเพื่อนบ้านกันและ

  • ทั้ง (a, b) หรือ (c, d) ไม่ได้เป็นของเส้นทางใด ๆ ที่เกิดขึ้น หากไม่พบสี่เหลี่ยมคู่ดังกล่าวบนกระดานทั้งหมด ให้ส่งคืน FAILURE /* ที่นี่ (a, b) และ (c, d) เป็นสองช่องแรกบนเส้นทางใหม่ที่จะสร้าง */

• สร้างการรวมตัวของต้นไม้สองต้นที่มี (a, b) และ (c, d)

• ทำซ้ำตราบเท่าที่เส้นทางปัจจุบันสามารถขยายได้ -

  • เปลี่ยนชื่อ (a, b) =(c, d)

• หาสี่เหลี่ยมข้างเคียงแบบสุ่ม (c, d) ของ (a, b) ที่ −

  • (c, d) ไม่ได้อยู่ในเส้นทางใด ๆ ที่สร้างขึ้น (รวมถึงเส้นทางปัจจุบัน)

  • เพื่อนบ้านเพียงคนเดียว (c, d) มีเส้นทางปัจจุบันที่สร้างขึ้นบางส่วนคือ (a, b)

• หากไม่พบเพื่อนบ้านดังกล่าว (c, d) เส้นทางจะไม่สามารถขยายเพิ่มเติมได้ ดังนั้นให้แยกลูป

• มิฉะนั้น ให้ทำการรวมกันของต้นไม้สองต้นที่ (a, b) และ (c, d) อยู่ร่วมกัน

• ตั้งค่าสถานะจุดสิ้นสุดของสองช่องที่จุดเริ่มต้นและจุดสิ้นสุดของเส้นทางใหม่

• คืนความสำเร็จ