บทความนี้อธิบายถึงปัญหาการครอบคลุมกระดานหมากรุกที่ใช้โดย Java ตามอัลกอริทึมการแบ่งพาร์ติชันและพิชิต แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
ในกระดานหมากรุกที่ประกอบด้วย 2^k * 2^k สี่เหลี่ยมมีสี่เหลี่ยมจัตุรัสที่แตกต่างจากที่อื่น ๆ หากมีการใช้โดมิโนรูปตัว L ต่อไปนี้เพื่อครอบคลุมสี่เหลี่ยมอื่น ๆ ยกเว้นสี่เหลี่ยมจัตุรัสพิเศษนี้วิธีการครอบคลุมพวกเขา โดมิโนรูปตัว L สี่ตัวแสดงอยู่ด้านล่าง:
สี่เหลี่ยมพิเศษในกระดานหมากรุกจะแสดงในรูป:
หลักการพื้นฐานของการใช้งานคือการแบ่ง 2^k * 2^k กระดานหมากรุกออกเป็นสี่ 2^(k - 1) * 2^(k - 1) บอร์ดย่อย สี่เหลี่ยมจัตุรัสพิเศษจะต้องอยู่ในหนึ่งในบอร์ดย่อย หากสี่เหลี่ยมจัตุรัสพิเศษอยู่ในบอร์ดย่อยบางแห่งให้ดำเนินการต่อเพื่อประมวลผลบอร์ดย่อยซ้ำจนกว่าจะมีเพียงหนึ่งตารางในบอร์ดย่อยนี้ หากสแควร์พิเศษไม่ได้อยู่ในบอร์ดย่อยบางแห่งให้ตั้งตำแหน่งที่สอดคล้องกันในบอร์ดย่อยเป็นหมายเลขโดมิโนให้แปลงบอร์ดโดยไม่ต้องใช้สี่เหลี่ยมพิเศษเป็นบอร์ดย่อยที่มีสี่เหลี่ยมพิเศษแล้วประมวลผลกระดานย่อยซ้ำ หลักการข้างต้นแสดงในรูป:
รหัสเฉพาะมีดังนี้:
การสาธิตแพ็คเกจหมากรุกระดับสาธารณะ { /*tr หมายถึงหมายเลขแถวของมุมซ้ายบนของกระดานหมากรุกจำนวนคอลัมน์ของมุมบนซ้ายของกระดานหมากรุกจำนวนแถวของกระดานหมากรุกพิเศษ DC ระบุจำนวนคอลัมน์ของกระดานหมากรุกพิเศษ } int t t = title ++; int s = size/2; // ครอบคลุมมุมบนซ้ายของกระดานหมากรุกถ้า (dr <tr + s && dc <tc + s) {// สแควร์พิเศษในกระดานหมากรุกกระดานนี้ (tr, tc, dr, dc, s); } else {// ไม่มีสแควร์พิเศษในบอร์ดนี้ครอบคลุมมุมล่างขวาด้วยโดมิโนรูปตัว L -number l [tr + s -1] [tr + s -1] = t; // ครอบคลุมส่วนที่เหลือของกระดานหมากรุกสี่เหลี่ยม (TR, TC, TC + S - 1, TC + S - 1, S); } // ครอบคลุมมุมบนขวาถ้า (dr <tr + s && dc> = tc + s) {// กระดานหมากรุกสแควร์พิเศษ (tr, tc + s, dr, dc, s); } else {// บอร์ดนี้มีสี่เหลี่ยมจัตุรัสพิเศษตอนเที่ยงครอบคลุมมุมซ้ายล่างด้วยโดมิโนรูปตัว L-number l [tr + s-1] [tc + s] = t; // ครอบคลุมส่วนที่เหลือของกระดานหมากรุกสี่เหลี่ยม (TR, TC + S, TR + S - 1, TC + S, S); } // ครอบคลุมกระดานหมากรุกมุมซ้ายล่างถ้า (dr> = tr + s && dc <tc + s) {// สแควร์พิเศษในกระดานหมากรุกบอร์ดนี้ (tr + s, tc, dr, dc, s); } else {// ไม่มีสแควร์พิเศษในบอร์ดนี้ครอบคลุมบอร์ดมุมขวาบน [tr + s] [tr + s -1] = t; // ครอบคลุมกระดานหมากรุกกำลังสอง (TR, TC, TC + S, TC + S - 1, S); } // ครอบคลุมกระดานหมากรุกมุมขวาล่าง (tr> = tr + s && dc> = tc + s) {// สแควร์พิเศษในกระดานหมากรุกกระดานนี้ (tr + s, tc + s, dr, dc, s); } else {// ไม่มีสแควร์พิเศษในบอร์ดนี้ให้ใช้โดมิโนรูปตัว L-number L เพื่อครอบคลุมบอร์ดมุมซ้ายบน [tr + s] [tc + s] = t; // ครอบคลุมกระดานหมากรุกกำลังสองที่เหลือ (tr + s, tc + s, tc + s, tc + s, s); }} @SuppressWarnings ("Static-Access") โมฆะคงที่สาธารณะหลัก (String args []) {System.out.println ("ผลการทดสอบ wulin.com:"); บอร์ด [2] [2] = 0; หมากรุก CH = ใหม่หมากรุก (); ch.chessboard (0, 0, 2, 2, ขนาด); สำหรับ (int i = 0; i <size; ++ i) {สำหรับ (int j = 0; j <size; j ++) {system.out.print (บอร์ด [i] [j]+""); } system.out.println (); }} ขนาด int สุดท้ายคงที่ = 4; ชื่อ int คงที่ = 1; บอร์ด int คงที่ [] [] = int ใหม่ [ขนาด] [ขนาด];}ผลการทำงาน:
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน