Mendeteksi urutan node dalam kotak

Mengingat gambar di bawah ini, saya perlu mendeteksi urutan paling optimal di papan (garis hijau). Garis biru / merah mewakili kemungkinan, tetapi bukan gerakan terbaik.

Berikut aturannya:

1. Anda dapat pindah ke ubin apa pun yang sama, dan tetangga Anda (diagonal valid)
2. Setelah Anda mengunjungi ubin, Anda tidak dapat mengunjunginya lagi.

Saya telah memikirkan perulangan melalui setiap simpul, dan melihat tetangganya, lalu secara rekursif melalui. Setelah saya menemukan kemungkinan langkah, saya bisa memasukkannya ke dalam struktur. Setelah semua kemungkinan gerakan ditemukan, saya hanya memilih langkah dengan jumlah simpul tertinggi. Menjadi lebih sulit ketika sebuah simpul memiliki lebih dari satu tetangga yang cocok.

Jadi, adakah algoritma yang bisa saya gunakan? Saya sedang memikirkan semacam banjir, tetapi itu tidak memenuhi aturan # 2.

Seperti yang diminta, berikut adalah video gameplay yang serupa. http://youtube.com/watch?v=eumnCTG0AE8

Anda dapat mempertimbangkan setiap kelompok simbol identik yang ditautkan (dan dengan ditautkan berarti Anda dapat melakukan perjalanan dari satu simbol ke simbol lainnya) sebagai grafik terpisah . Untuk setiap grafik, terapkan Depth First Search (DFS) mulai dari setiap node dalam grafik yang belum menjadi bagian dari jalur terpanjang untuk grafik itu . Setiap kali Anda mencapai jalan buntu saat menerapkan DFS, periksa untuk melihat apakah jalur yang baru saja Anda lewati lebih panjang dari maksimum global yang Anda temukan sejauh ini. Jika ya, simpan sebagai jalur terpanjang baru.

Anda akan melihat bahwa pada paragraf sebelumnya saya sebutkan menerapkan DFS beberapa kali untuk setiap grafik. DFS tunggal yang dijalankan pada grafik tidak akan cukup. Pertimbangkan kasus khusus ini:

    1
1 1 1
    1
    1
    1
    1

Jika kebetulan Anda pertama kali menjalankan DFS pada grafik ini di simpul paling atas, Anda akan menemukan jalur terpanjang yang mungkin sebagai garis vertikal, tetapi itu tidak benar. Ini akan terjadi setiap kali Anda memulai algoritme DFS dalam sebuah simpul yang berada di suatu tempat di dalam jalur yang dihasilkan atau bukan bagian dari itu sama sekali. Apa yang perlu Anda lakukan dalam contoh khusus ini juga memulai algoritma DFS dari simpul paling kiri di baris kedua. Itu akan menemukan jalan yang benar. Secara umum, Anda harus menjalankan algoritma DFS di setiap node yang saat ini bukan bagian dari jalur terpanjang untuk grafik itu, seperti yang dinyatakan di atas.

Skenario kasus terburuk absolut untuk algoritma ini adalah papan penuh atau sebagian besar diisi dengan jenis simbol tunggal, namun itu tidak mungkin terjadi dalam permainan. Juga, berhati-hatilah bagaimana Anda menyimpan jalur terpanjang untuk setiap grafik. Jika Anda tidak mengoptimalkan bit ini, Anda mungkin lebih baik hanya memanggil DFS untuk setiap node di atas panggung. Dengan asumsi bahwa Anda tidak bekerja dengan papan yang sangat besar dan kecepatan itu bukan masalah besar, solusi ini harus cukup cepat.

Secara teknis, dengan memecah papan Anda menjadi grafik terpisah Anda berakhir dengan beberapa " masalah jalur terpanjang ". Seperti yang dapat kita lihat dari contoh Anda, Anda dapat memiliki siklus dalam grafik Anda (misalnya, memiliki semua simbol di luar panggung dari jenis yang sama), yang berarti bahwa dalam masalah khusus ini Anda perlu menemukan jalur terpanjang dalam beberapa grafik tidak berarah siklik, yang tidak dapat dilakukan dalam waktu polinomial .

Jika Anda merasa ini terlalu lambat, lihat jawaban ini di StackOverflow untuk detail lebih lanjut tentang cara mengoptimalkan "Masalah Jalur Terpanjang" individu.