Latar Belakang

Saya telah membangun rintangan sederhana dengan menempatkan kotak di ruangan persegi panjang. Sekarang saya ingin menghitung jumlah cara yang pada dasarnya berbeda untuk menyelesaikannya. Saya ingin Anda menulis saya program untuk itu.

Memasukkan

Input Anda adalah array karakter persegi panjang yang tidak kosong .#. Titik .- titik itu adalah ruang kosong, dan #merupakan penghalang.

Sebuah jalan melalui rintangan kursus dimulai di sudut kiri atas dan berakhir di sudut kanan bawah, dan pergi hanya kanan atau ke bawah. Selain itu, jalur yang valid tidak dapat melewati rintangan. Berikut ini beberapa contoh yang diambil dengan +-karakter:

Valid path  Invalid path  Invalid path  Invalid path
++........   ++........    +++++.....    ..+.......
.++++++#..   .+.....#..    ....+++#++    ..++...#..
......+#..   .+.++++#..    .......#.+    ...+++.#..
....#.++++   .+++#.++++    ....#....+    ....#+....

Dua jalur pada dasarnya serupa ¹ jika satu dapat diubah menjadi yang lain dengan memindahkan satu +per satu. Jalur perantara juga harus valid, sehingga Anda tidak dapat membengkokkan jalur melewati rintangan. Sebagai contoh, dua jalur pertama di sini pada dasarnya serupa, tetapi yang ketiga pada dasarnya berbeda dari mereka, karena tidak dapat digoyahkan atas dua rintangan:

++........   +.........   +++++++++.
.+++++.#..   ++.....#..   .......#+.
.....+.#..   .++++++#..   .......#++
....#+++++   ....#.++++   ....#....+

Keluaran

Output Anda adalah jumlah jalur yang pada dasarnya berbeda melalui rintangan. Dengan kata lain, jika semua jalur yang valid dibagi ke dalam kelas yang pada dasarnya jalur yang sama, outputnya adalah jumlah kelas. Perhatikan bahwa angka ini mungkin 0, jika tidak ada jalur yang valid.

Aturan dan penilaian

Anda dapat menulis program atau fungsi lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan. Tidak ada batasan waktu, kecuali bahwa Anda harus mengevaluasi program Anda pada setiap test case sebelum mengirimkannya.

Uji kasus

....
....
.... => 1

...#
....
...# => 0

#..#
..#.
.... => 0

......
......
..##..
......
...... => 2

......
...#..
......
..#...
#..... => 3

......
..#...
......
....#.
#..... => 4

.......
##.....
....###
...#...
..##.#.
#....#.
..#.... => 0

......#.
..##....
...#....
.......#
....#...
.##...#.
....#...
##...... => 7

.........
.#.#.#.#.
.........
#.#...#.#
.........
.#.#.#.#.
......... => 17

..........
.#........
..........
.....#....
#.........
........#.
......#...
.......... => 10

.........
.#.......
.........
...#.....
.........
.....#...
.........
.......#.
......... => 16

_{1 Istilah teknis yang benar adalah "homotopic" .}

Siput , 53 49 byte

A^
\.+d!{.l\.+a3(.|~c!~}\.+r!(.u\.+e(.|~},\.,=~d~

Untuk sekali ini, aku tidak harus menggunakan t, instruksi teleport yang ditakuti. Akibatnya, kasus uji selesai secara instan alih-alih mengambil waktu berabad-abad.

Tidak Disatukan:

A^
r\.+
{
    d\.+
    !{ r\.u \.+ a3 (.|~)}
    r\.+
    !{ d\.l \.+ a3 (.|~)}
},
d\.,
!(dr .)

Opsi A^berarti mulai di sudut kiri atas dan menghitung semua jalur yang cocok. Gagasan utama adalah untuk memeriksa kondisi kanonisitas untuk jalur. Sejujurnya saya tidak berharap itu bekerja, tetapi memaku kasus uji, jadi .... Apa yang mencoba untuk memeriksa adalah bahwa, dalam jalur saat ini, rute paling tamak telah dipilih, yaitu berjalan sebanyak mungkin sebanyak mungkin , turun sebanyak mungkin, dll. tanpa melewati rintangan apa pun. Hal ini dilakukan dengan memeriksa, setelah bergerak ke kanan 1 kali atau lebih dan kemudian turun 1 kali atau lebih, bahwa bujur sangkar berikutnya (yang harus ke kanan) tidak dapat dicapai dengan berjalan sekali lagi di segmen kanan sebelumnya. Kondisi analog juga diperiksa setelah bergerak ke kanan dan ke bawah.

Python 2, 170 131 112 byte

def f(C,t=1):i="#".join(C).find("#")+1;return([]<C)*(i<1or(i<t
and f([r[i:]for r in C],t-i))+(i>1)*f(C[1:],i-1))

Sebuah fungsi,, fmengambil rintangan sebagai daftar baris, dan mengembalikan jumlah jalur yang pada dasarnya berbeda.

Penjelasan

Konsep dasarnya adalah ini: Kami memilih hambatan tertentu, o , sehingga tidak ada hambatan lain di dalam kotak yang membatasi o dan sudut kiri atas.

+--+....
|..|....  
+--#<==== o
.....#..
.#......
........

Kami kemudian mempertimbangkan dua sub-kursus ke timur dan ke selatan dari o . Kami hanya mempertimbangkan salah satu dari sub-program ini jika , ada jalur antara titik awal dan titik masuk ke masing-masing wilayah ini, dan semua jalur yang mengarah ke titik yang sama pada dasarnya sama, maka jumlah di atas adalah lengkap sejumlah jalur dasarnya berbeda di seluruh kursus. o benar-benar dapat dilintasi dari arah yang mengarah ke mereka, yaitu, menyeberang dari utara untuk menuju ke timur, dan menyeberang dari barat untuk sampai ke selatan. Kami memecahkan masalah untuk masing-masing sub-program yang dipilih, dan mengembalikan jumlah hasilnya. Angka-angka ini sesuai dengan jumlah jalur yang pada dasarnya berbeda ketika melintasi o dari kiri dan dari kanan, masing-masing, oleh karena itu dua set jalur yang dihasilkan pada dasarnya berbeda. Karena tidak ada hambatan antara titik awal dan o

                               A
_
........       ...|////      |....
........       ...|////      |....
...#....  -->  ...#////  -->  ....
.#....#.       .#..//#/       ..#.
........       ....////       ....

   |                           |
   v                           v
                  B
........       ___
........       .#....#.
___#....  -->  ........  -->   +
/#////#/       
////////       

Hal-hal sedikit rumit oleh kenyataan bahwa rintangan saja tidak menyampaikan semua informasi yang dibutuhkan. Sebagai contoh, perhatikan saja B dalam diagram di atas. Diambil dengan sendirinya, kita tidak dapat menentukan apakah masing-masing rintangan dapat dilintasi dari utara. Jika B adalah jalur input, maka, karena semua jalur mulai dari sudut kiri atas, tidak ada rintangan yang dapat dilintasi dari utara, tetapi, karena kita dapat mencapai B dari kedua sisi hambatan kiri saat melintasi o dari timur , kita harus memperlakukan rintangan ini seolah-olah dapat dilintasi dari utara ketika menyelesaikan jalurnya; Namun, hal yang sama tidak berlaku untuk hambatan yang benar, yang tidak dapat dilintasi dari arah ini.

Kami memberikan informasi tambahan ini dengan menentukan, bersama dengan rintangan, jumlah karakter di sepanjang baris pertama, mulai dari kiri, di mana jalur dapat dimulai. Dalam diagram di atas, ini dinyatakan sebagai garis padat di sebelah setiap jalur. Sementara, secara teknis, kita juga perlu menentukan jumlah karakter yang sesuai di sepanjang kolom pertama jalur yang dapat dimulai, seperti dalam kasus sub-kursus A , dalam praktiknya kita selalu memilih hambatan tertinggi, sehingga informasi ini tidak diperlukan .

Pemilihan aktual dari o adalah sebagai berikut: Kami berpura-pura bahwa setiap baris, selain yang terakhir, diikuti oleh rintangan (yaitu, telah #ditambahkan ke dalamnya), dan memilih rintangan pertama dalam kursus yang dihasilkan, dalam urutan membaca. Untuk baris (selain yang terakhir) yang tidak memiliki hambatan pada awalnya, ini secara efektif berarti bahwa kita melewatkannya (sambil mencatat bahwa jalur di bawah ini dapat dimulai dari karakter apa pun di sepanjang baris atas). Akhirnya, kita berakhir dengan kursus yang memiliki satu baris tanpa hambatan, yang hanya ada satu jalur yang mungkin.

CJam, 85 84 82 81 80 79 byte

qN/:Q,(Qz,(:R_T]2/e~e!{'#Qs@{\(\@>}%s-},{_}{(a\L{@+_@\-_{2$\f.=0fe=2&},}h;}w;],

Cobalah online. Atau jalankan seluruh test suite.

Efisiensi dari solusi ini mungkin cukup mengerikan tetapi menyelesaikan setiap test case dalam beberapa detik.

Penjelasan

Saya harus menambahkan uraian lengkap kode nanti, tetapi ide algoritmiknya adalah ini:

• Biarkan lebar dan tinggi kisi menjadi Wdan H, masing-masing.
• Kami menghasilkan semua jalur yang mungkin sebagai permutasi yang berbeda dari W-1salinan0 dan H-1salinan W-1(di mana 0merupakan langkah horizontal dan W-1langkah vertikal). Kami berjalan di semua jalur tersebut dengan berulang kali mengambil elemen pertama dari grid dan kemudian melewatkan stepsel dalam urutan membaca (di mana stepada 0atau W-1). Kami membuang semua jalur yang berisi a# .
• Lalu kami berulang kali menghapus satu grup jalur yang sama (yang akan menjadi semua jalur yang mirip dengan yang pertama dari jalur yang tersisa). Memeriksa jalur yang sama akan sedikit lebih mudah dengan sedikit merelaksasi kondisi untuk mereka: daripada memeriksa apakah adax bergerak, kami memeriksa apakah jalurnya berbeda persis di dua tempat. Jika itu yang terjadi, kedua tempat itu akan ditukar dengan gerakan vertikal dan horizontal. Ini menyebabkan seluruh segmen di antara gerakan-gerakan itu digeser secara diagonal oleh satu sel. Tetapi jika kedua jalur itu valid, menggeser bagian mana pun dari jalur dengan satu sel secara diagonal tidak dapat melintasi penghalang, sehingga keduanya serupa. Kami masih perlu menemukan penutupan transitif, jadi kami terus melakukan itu sampai kami tidak menemukan jalan yang sama sebelum pindah ke grup berikutnya.
• Akhirnya, kami menghitung grup yang kami temukan, yang kami tinggalkan di bagian bawah tumpukan.