Permainan sambung nombor dalam C/C++?

Permainan - Katakan terdapat susunan n × n segi empat sama. Antaranya, beberapa petak kosong, ada yang pepejal, dan beberapa petak tidak pepejal ditetapkan oleh integer 1, 2, 3,... Setiap integer memegang atau menduduki betul-betul dua petak berbeza pada papan. Tugas pemain adalah untuk menyambungkan dua kejadian setiap integer di papan dengan bantuan laluan mudah yang hanya melaksanakan pergerakan mendatar dan menegak. Dua laluan berbeza tidak dibenarkan bersilang antara satu sama lain. Tiada laluan boleh mengandungi sebarang blok pepejal (blok pepejal tidak dibenarkan pada mana-mana laluan). Akhir sekali, semua petak bukan pepejal mesti diisi dengan laluan.

Algoritma - Untuk membina teka-teki rawak yang cekap dengan saiz papan n × n yang diberikan, kami mula-mula menjana laluan mudah rawak yang saling berpisah pada papan hitam. Jika beberapa blok terpencil masih berada di luar semua laluan yang dijana, tandakan blok terpencil ini sebagai pepejal (dilarang). Seterusnya, kami menyediakan titik akhir laluan dan senarai petak pepejal sebagai teka-teki.

Jadi kami mula-mula menjana penyelesaian dan kemudian mengira teka-teki berdasarkan penyelesaian itu. Laluan dan petak pepejal memisahkan n × n plat. Kami melaksanakan dan mencari struktur data untuk menjana partition ini. Struktur data mengendalikan subset set n^2 petak pada papan catur.

Pseudokod

• Kedudukan petak (a, b) dan (c, d) secara rawak pada papan catur, supaya -

  • (a, b) dan (c, d) adalah berjiran antara satu sama lain, Dan

  • (a, b) mahupun (c, d) tidak tergolong dalam mana-mana laluan yang dijana setakat ini. jika dalam Seluruh papan, mengembalikan GAGAL /* Di sini, (a​​, b) dan (c, d) ialah dua petak pertama di laluan baharu menubuhkan. */

• Kesatuan dua pokok pencarian kesatuan, yang mengandungi (a, b) dan (c, d).

• Ulang sehingga laluan semasa boleh dipanjangkan -

  Namakan semula (a, b) = (c, d).

Cari petak bersebelahan secara rawak (c, d) (a, b) supaya -

• (c, d) tidak tergolong dalam mana-mana laluan yang dijana setakat ini (termasuk laluan semasa)

• Satu-satunya jiran (c, d) pada laluan semasa pembinaan separa ialah (a, b).

Jika tiada jiran sedemikian (c,d) ditemui, laluan itu tidak boleh dipanjangkan lagi, sekali gus memutuskan kitaran

Jika tidak, kedua-dua (a, b) dan (c, d) adalah milik dan cari pokok itu.

Tetapkan bendera titik akhir bagi dua blok yang terletak di permulaan dan penghujung laluan baharu.

Kembali kepada KEJAYAAN

Atas ialah kandungan terperinci Permainan sambung nombor dalam C/C++?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!