Ayunkan Pohon-Pohon dengan Grapple Hook Anda

8

Anda telah menemukan jalur melalui hutan dan sekarang berencana untuk bepergian di sepanjang jalan itu. Namun, tepat sebelum Anda memulai perjalanan Anda, tanah berubah menjadi lava.

Anda berhasil berlari ke pohon terdekat (pohon-pohon itu entah kenapa tidak terbakar), tetapi sekarang Anda dihadapkan pada masalah: bagaimana Anda bisa keluar dari hutan ketika lantainya lava? Jawabannya menghantam Anda seperti ide yang bagus untuk tantangan pemrograman - Anda dapat menggunakan pengait ajaib Anda (dibuat dari sepotong kano sebelumnya) untuk berayun melalui pohon dan cabang!

Namun, Anda tidak yakin mana pohon-pohon dan cabang yang Anda butuhkan untuk mengayunkan ke sana. Untungnya, Anda memiliki keterampilan pemrograman, sehingga Anda memutuskan untuk menggambar program di lengan Anda untuk memberi tahu Anda pohon mana yang akan diayun. Namun, tidak banyak area permukaan di lengan Anda, jadi Anda harus membuat program sekecil mungkin.

Kami dapat mewakili hutan menggunakan array noleh m. Karakter berikut akan membentuk array:

  • T: Pohon. Anda bisa mendarat di sini. Anda tidak dapat menggunakan pengait Anda pada ini. Anda bisa berayun melalui ini.
  • P: Fungsinya sama dengan T. Anda mulai dari sini.
  • Q: Fungsinya sama dengan T. Inilah tujuannya.
  • +: Cabang. Anda tidak dapat mendarat di sini. Anda dapat menggunakan pengait Anda pada ini. Anda bisa berayun melalui ini.
  • *: Laba-laba pemakan manusia. Jika Anda mendarat di sini, Anda mati. Jika Anda menggunakan pengait Anda pada ini, Anda mati. Jika Anda mengayunkan ini, Anda mati.
  • -: Tanah biasa, dengan kata lain, lava. Anda tidak dapat mendarat di sini. Anda tidak dapat menggunakan pengait Anda pada ini. Anda bisa berayun melalui ini. Semua area di luar array yang diberikan adalah tipe ini.

Berikut adalah contoh dari bagaimana hutan itu terlihat:

               y
----T---+------12
---------------11
----T---+---T--10
---------------9
T-+-T-+-T------8
---------------7
------------+--6
----+----------5
+-------+------4
---------------3
----P---+-*-Q--2
---------------1
T-+-T-+-T------0
012345678911111
x         01234

Saya akan merujuk ke koordinat dengan notasi (x,y), seperti yang ditunjukkan pada sumbu.

Anda mulai dari Pdan harus membuat jalan ke Q. Untuk melakukan ini, Anda berayun dari pohon Tke pohon Tmenggunakan cabang +. Anda dapat melampirkan pengait Anda pada cabang apa pun yang ortogonal bagi Anda - yaitu, cabang yang berada pada posisi x yang sama atau posisi y Anda berada. Misalnya, jika Anda berada pada posisi (4,8)di hutan contoh, Anda bisa melampirkan kait bergulat Anda untuk posisi (2,8), (6,8)atau (4,5). Anda dapat melampirkan ini bahkan jika ada pohon atau cabang lain di antara Anda dan cabang.

Setelah Anda memasang kait pengait ke cabang, Anda akan menempuh jarak ke arah cabang yang sama dengan dua kali jarak antara posisi awal dan cabang. Dengan kata lain, posisi akhir Anda akan memiliki jarak yang sama dari cabang dengan posisi awal Anda, tepat di sisi yang berlawanan. Definisi yang lebih formal tentang bagaimana gerakan itu ada di bawah. Subskrip dari vadalah posisi akhir, uadalah posisi awal, dan badalah posisi cabang.

(xv,yv)=(2xb−xu,2yb−yu)

Perhatikan bahwa jika ada laba-laba antara posisi awal Anda dan posisi akhir Anda, Anda tidak bisa pergi ke sana. Misalnya, dalam contoh hutan ayunan dari (4,2)ke (12,2)tidak dimungkinkan karena Anda akan bertemu laba-laba di (10,2).

Tujuannya adalah, menggunakan metode berayun melalui cabang ini, untuk melakukan perjalanan dari titik Pke titik Qdalam ayunan sesedikit mungkin. Misalnya, di hutan contoh, jalur terpendek adalah:

  1. Dari (4,2)ke (4,8)menggunakan(4,5)
  2. Dari (4,8)ke (0,8)menggunakan(2,8)
  3. Dari (0,8)ke (0,0)menggunakan(0,4)
  4. Dari (0,0)ke (4,0)menggunakan(2,0)
  5. Dari (4,0)ke (4,10)menggunakan(4,5)
  6. Dari (4,10)ke (12,10)menggunakan(8,10)
  7. Dari (12,10)ke (12,2)menggunakan(12,6)

Memasukkan

Input berasal dari metode mana pun yang nyaman (STDIN, argumen baris perintah raw_input(), dll.), Kecuali mungkin tidak diinisialisasi sebagai variabel. Input dimulai dengan dua bilangan bulat yang dipisahkan koma ndan mmewakili ukuran papan, lalu spasi, dan kemudian hutan sebagai string panjang tunggal. Misalnya, contoh hutan sebagai input akan terlihat seperti ini:

15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------

Keluaran

Keluarkan daftar tuple yang dipisahkan koma yang menunjukkan koordinat cabang yang harus Anda ayunkan. Misalnya, untuk input di atas, outputnya adalah:

4,5 2,8 0,4 2,0 4,5 8,10 12,6

Anda mungkin telah memperhatikan bahwa ini bukan satu-satunya jalan terpendek melalui hutan - memang, pergi ke (8,8), turun ke (8,0), ke kiri (4,0)dan melanjutkan seperti biasa dari sana mengambil jumlah ayunan yang persis sama. Dalam kasus ini, program Anda dapat menampilkan salah satu jalur terpendek. Jadi hasilnya:

4,5 6,8 8,4 6,0 4,5 8,10 12,6

juga diperbolehkan. Ini adalah kode-golf , jadi entri dengan jumlah byte terpendek akan menang. Jika Anda memiliki pertanyaan atau penjelasan saya tidak jelas, tanyakan di komentar.

code-golf graph-theory Absinth
sumber
Input contoh Anda harus mulai 15,13karena ukuran array 13 x 15.
Howard
@ Howard Diperbaiki. Terima kasih.
absinthe

Jawaban:

4

GolfScript, 196 karakter

' '/(~):H;,):W(\~/-1%'*':S*:^{:I,,{I=79>},:A{{[\1$1$+2/]}+A/}%{)I=43=\$.~I<>S&!\~+1&!&&},}:C~S^W/zip*C{{.H/\H%W*+}%}%+:B;^'P'?]]{{(B{0=1$=},\;\`{\1>\+}+/}%.{0=^=81=},:|!}do;|0=1>-1%{.W%','@W/' '}/

Sepotong kode GolfScript yang mengerikan - namun berfungsi seperti yang diinginkan. Algoritma tidak optimal tetapi cukup cepat, contohnya berjalan jauh di bawah satu detik di komputer saya.

> 15,13 ----T---+-------------------------T---+---T-----------------T-+-T-+-T---------------------------------+------+----------+-------+-------------------------P---+-*-Q-----------------T-+-T-+-T------
4,5 2,8 0,4 2,0 4,5 8,10 12,6
Howard
sumber