Saya baru mengenal pemrograman kompetitif, dan saya sering memperhatikan, banyak pembuat kode hebat memiliki empat baris ini dalam kode mereka (terutama yang melibatkan array):
int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int diK[] = { -2, -2, -1, 1, 2, 2, 1, -1 };
int djK[] = { -1, 1, 2, 2, 1, -1, -2, -2 };
Apa arti sebenarnya dari hal ini dan untuk apa teknik digunakan?
d={0,1,0,-1,0}
untuk ini: pasangan barang untukd[i], d[i+1]
memberi saya empat arah mata angin.Jawaban:
Ini adalah teknik untuk menyandikan semua arah sebagai array - setiap pasangan
di[i],dj[i]
memiliki arah yang berbeda.Jika kita membayangkan kita memiliki bagian di lokasi x, y, dan kita ingin menambahkan pada x dan nilai y untuk memindahkannya ke lokasi terdekat, 1,0 di timur, -1,0 barat, 0,1 di selatan, 0, -1 adalah utara dan seterusnya.
(Di sini saya telah mengatakan kiri atas adalah 0,0 dan kanan bawah adalah 4,4 dan menunjukkan pergerakan apa yang akan dilakukan setiap indeks array dari titik pusat, X, di 2,2.)
Cara pengaturannya, jika Anda melakukan
^1
(^
menjadi XOR bitwise) pada indeks Anda mendapatkan arah yang berlawanan - 0 dan 1 berlawanan, 2 dan 3 berlawanan dan seterusnya. (Cara lain untuk mengaturnya adalah dengan berjalan searah jarum jam mulai dari utara - lalu^4
membawa Anda ke arah yang berlawanan.)Sekarang Anda dapat menguji semua arah dari titik tertentu dengan mengulang array
di
dandj
, alih-alih perlu menulis setiap arah pada barisnya sendiri (untuk total delapan!) (Jangan lupa untuk melakukan pemeriksaan batas :))diK
dandjK
membentuk semua arah ksatria alih-alih semua arah yang berdekatan. Di sini,^1
akan membalik sepanjang satu sumbu,^4
akan memberikan lompatan ksatria yang berlawanan.sumber
x,y
tupel dalam ruang 2D. Untuk setiap pasangan,di[i], dj[i]
tambahkan kex,y
dan Anda akanx,y
dialihkan ke setiap arah satu per satu. Apakah itu masuk akal?Bagi mereka yang merasa penjelasan Patashu sulit diikuti, saya akan mencoba menjelaskan.
Bayangkan Anda mencoba mempertimbangkan setiap langkah yang mungkin dari titik tertentu di papan catur.
Jika Anda mengulang array di dan dj, menafsirkan nilai di sebagai offset x dan nilai dj sebagai offset y, Anda mencakup setiap kemungkinan 8 arah.
Dengan asumsi x positif timur dan positif y selatan (seperti dalam jawaban Patashu), Anda mendapatkan yang berikut;
Array diK dan djK dapat diinterpretasikan dengan cara yang sama untuk menetapkan kemungkinan gerakan untuk bidak Knight. Jika Anda tidak terbiasa dengan catur, Kuda bergerak dalam pola L - dua kotak dalam satu arah, dan kemudian satu kotak pada sudut siku-siku (atau sebaliknya).
sumber
Potongan kecil kode untuk memeriksa jumlah gerakan yang mungkin dilakukan ke segala arah, yang menggunakan array yang ditentukan.
sumber