Apa pentingnya menginisialisasi array arah di bawah ini dengan nilai yang diberikan saat mengembangkan program catur?

106

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?

ejjyrex.dll
sumber
5
Saya sering menggunakan d={0,1,0,-1,0}untuk ini: pasangan barang untuk d[i], d[i+1]memberi saya empat arah mata angin.
dasblinkenlight
14
Ini adalah pertanyaan yang sangat bagus. ... Apakah ada yang bisa dilakukan tentang judul itu?
luser droog
7
Jadi Anda tidak berpikir untuk menyebutkan bahwa kode ini berasal dari mesin catur? Juga Anda tidak berpikir untuk melihat sendiri bagaimana nilai-nilai ini digunakan?
trojanfoe
15
"banyak dari pembuat kode yang hebat memiliki empat baris ini [...]" - Saya bingung di sini, tetapi jika mereka adalah pembuat kode yang hebat, kode mereka tidak akan membuat Anda bertanya-tanya "apa konstruksi itu ?!"
utnapistim
6
@utnapistim Saat menulis sebagian besar kode, Anda benar, tetapi di sini, Anda kehilangan intinya. Kasus ini adalah pengecualian yang sah untuk aturan itu. Jika Anda menulis kode untuk kompetisi dan di bawah batasan waktu, quick-and-dirty hampir selalu lebih baik daripada clean-and-maintainable. Dalam hal ini dibaca untuk Anda, sekarang benar-benar adalah semua yang penting. Seorang pembuat kode yang hebat dengan sangat baik menulis kekacauan yang tidak bisa terbaca dalam konteks ini , bahkan jika sebagian besar kode reguler mereka sangat mudah dibaca dan dipelihara.
Ben Lee

Jawaban:

84

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.)

.....
.536.
.1X0.
.724.
.....

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 ^4membawa Anda ke arah yang berlawanan.)

Sekarang Anda dapat menguji semua arah dari titik tertentu dengan mengulang array didan dj, alih-alih perlu menulis setiap arah pada barisnya sendiri (untuk total delapan!) (Jangan lupa untuk melakukan pemeriksaan batas :))

diKdan djKmembentuk semua arah ksatria alih-alih semua arah yang berdekatan. Di sini, ^1akan membalik sepanjang satu sumbu, ^4akan memberikan lompatan ksatria yang berlawanan.

.7.6.
0...5
..K..
1...4
.2.3.
Patashu
sumber
3
apa itu 'arah ksatria'?
David
4
Oh, ksatria seperti itu.
David
1
Terima kasih banyak atas jawaban Anda .. Bisakah Anda menautkan saya atau mungkin menunjukkan beberapa kode untuk mengilustrasikannya dengan lebih baik .. (Saya agak pemula .. jika Anda bisa mengerti :) Terima kasih lagi
ejjyrex
1
Saya memuji upaya Patashu untuk menjawab. Meskipun tampaknya banyak yang telah memahami penjelasannya, saya belum dapat memahaminya dengan baik. Jika ada yang bisa menambahkan apa yang telah dikatakan, saya akan sangat berterima kasih.
deepak
1
@deepak Bayangkan sebuah posisi diwakili oleh x,ytupel dalam ruang 2D. Untuk setiap pasangan, di[i], dj[i]tambahkan ke x,ydan Anda akan x,ydialihkan ke setiap arah satu per satu. Apakah itu masuk akal?
Patashu
64

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;

  | di / x | dj / y | Arah
- + ------ + ------ + -----------
0 | 1 | 0 | timur
1 | -1 | 0 | Barat
2 | 0 | 1 | Selatan
3 | 0 | -1 | utara
4 | 1 | 1 | tenggara
5 | -1 | -1 | Barat laut
6 | 1 | -1 | timur laut
7 | -1 | 1 | barat daya

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).

  | diK / x | djK / y | Arah
- + ------- + ------- + ----------------
0 | -2 | -1 | 2 barat, 1 utara
1 | -2 | 1 | 2 barat, 1 selatan
2 | -1 | 2 | 1 barat, 2 selatan
3 | 1 | 2 | 1 timur, 2 selatan
4 | 2 | 1 | 2 timur, 1 selatan
5 | 2 | -1 | 2 timur, 1 utara
6 | 1 | -2 | 1 timur, 2 utara
7 | -1 | -2 | 1 barat, 2 utara
James Holderness
sumber
1

Potongan kecil kode untuk memeriksa jumlah gerakan yang mungkin dilakukan ke segala arah, yang menggunakan array yang ditentukan.

int di[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dj[] = { 0, 0, 1, -1, 1, -1, -1, 1 };
int movesPossible[8];
int move = 0;
int posx, posy; // position of the figure we are checking

for (int d=0; d<8; d++) {
  for (move = 1; board.getElt(posx+di[d]*move, posy+dj[d]*move)==EMPTY; move++) ;
  movesPossible[d] = move-1;
}
Dariusz
sumber