Hackerrank's Queen's Attack II

Question

https://www.hackerrank.com/challenges/queens-attack-2/problem

Bir vezir bir nxn satranç tahtası üzerinde duruyor. Satranç tahtasının satırları 1'den n'ye kadar numaralandırılır ve aşağıdan yukarıya doğru gider; sütunları soldan sağa giderek 1'den n'ye kadar numaralandırılmıştır. Tahtadaki her kare, karenin bulunduğu satır, r ve sütunu (c) tanımlayan bir demet (r, c) ile gösterilir.

Vezir pozisyonda duruyor (rq, cq) ve tek bir hareketle herhangi bir kareye sekiz yönden (sol, sağ, yukarı, aşağı veya dört köşegen) saldırabilir. Aşağıdaki şemada, yeşil daireler kraliçenin saldırabileceği tüm hücreleri göstermektedir (4, 4):

Var \$k\$satranç tahtasındaki vezirin kendisine giden yolunu engelleyen herhangi bir kareye saldırmasını engelleyen engeller. Örneğin, konumdaki bir engel \$(3,5)\$Yukarıdaki diyagramda kraliçenin hücrelere saldırmasını önleyecektir \$(3,5)\$, \$(2,6)\$ve \$(1,7)\$:

Kraliçenin konumu ve tüm engellerin yerleri göz önüne alındığında, \ ' deki konumundan vezirinin saldırabileceği karelerin sayısını bulun ve yazdırın.$(r_q,c_q)\$.

Giriş Formatı

İlk satır, ilgili değerleri açıklayan boşlukla ayrılmış iki tamsayı içerir \$n\$(kartın yan uzunluğu) ve \$k\$ (engellerin sayısı).

Sonraki satır, ilgili değerleri açıklayan boşlukla ayrılmış iki tamsayı içerir \$r_q\$ve \$c_q\$, kraliçenin konumunu belirtir.

Her satır \$i\$arasında \$k\$sonraki satırlar, ilgili değerleri açıklayan iki boşlukla ayrılmış tamsayı içerir \$r_i\$arasında \$c_i\$ve engelin konumunu belirtir \$i\$.

Kısıtlamalar

\$ 0 \leq n \leq 100000\$

\$ 0 \leq k \leq 100000\$

Tek bir hücre birden fazla engel içerebilir; ancak, pozisyonda asla bir engel olmayacağı garantilidir \$(r_q,c_q)\$ kraliçenin bulunduğu yer.

Çıkış formatı

Vezirin konumdan saldırabileceği kare sayısını yazdırın.

Örnek Giriş 0

\$4\$ \$0\$

\$4\$ \$4\$

Örnek Çıktı 0

\$9\$

Açıklama 0

Kraliçe pozisyonunda duruyor \$(4,4)\$bir \$4\$x \$4\$ engelsiz satranç tahtası:

Daha sonra o olduğunu pozisyondan saldırabilir kareler sayısını yazdırmak \$9\$.

Benim yaklaşımım:

N çok yüksek olduğunda kaynak yoğun olacağı için, kraliçeler yolundaki her noktayı yinelemek yerine, yolları 8 farklı yöne ayırmaya gittim (yukarı sola, yukarı, sağa, sağa, vb.).

int u, d, l, r, ul, ur, dl, dr;
u = d = l = r = ul = ur = dl = dr = 0;
bool modified[8] = { false };

Daha sonra, kraliçelerin x = engellerin x veya kraliçelerin y = engellerin y olup olmadığını kontrol ederek yolda bir engel olup olmadığını ve kraliçelerin dikey / yatay yolunda olup olmadığını kontrol ederek mesafeyi delta - 1 ve vezir yolunda olmak için noktaların 1 veya -1 eğimi olması gerektiğinden bildiğim çapraz noktaları bulmak için | vezirin y - engelinin y | = | vezirin x - engelin x | ve eğer bu x veya y arasındaki deltayı iş olarak bulduğumdan ve eğer hiçbir engel yoksa, mesafeyi bulmak için sadece kenarı kullanırdım. Sadece engelin yolda olup olmadığını kontrol ediyorum, ardından olası noktaları hesaplamak yerine yönü çözülmüş olarak işaretledim, böylece eğer işaretli değilse, yolda hiçbir engel olmadığı anlamına gelir, böylece kenardan uzaklığı bulabilirim:

if (!modified[0]) u = n - qy;
if (!modified[1]) d = qy - 1;
if (!modified[2]) l = qx - 1;
if (!modified[3]) r = n - qx;
if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

Dağınık stil için özür dilerim, bu stackoverflow / stackexchange'de ilk kez.

Tam kod:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int queensAttack(const int &n, const int &k, const int & qy, const int & qx, const vector<vector<int>> &obstacles) {
    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;          
    bool modified[8] = { false };                   //if modified is still false after looping through obstacles check that means no obstacle at path

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen
        int temp{};
        if (obstacles[i][1] == qx) {                //if obstacle x = queen x than they are on same column
            if (obstacles[i][0] > qy) {             //check if its above or below queen
                temp = obstacles[i][0] - qy - 1;    
                if (modified[0] && u > temp || !modified[0]) {    //only assign distance if it was never assigned before or less than it  
                    u = temp;
                }
                modified[0] = true;
            }
            else {
                temp = qy - obstacles[i][0] - 1;
                if (modified[1] && d > temp || !modified[1]) {
                    d = temp;
                }
                modified[1] = true;
            }
        }
        if (obstacles[i][0] == qy) {
            if (obstacles[i][1] < qx) {
                temp = qx - obstacles[i][1] - 1;
                if (modified[2] && l > temp || !modified[2]) {
                    l = temp;
                }
                modified[2] = true;
            }
            else {
                temp = obstacles[i][1] - qx - 1;
                if (modified[3] && r > temp || !modified[3]) {
                    r = temp;
                }
                modified[3] = true;
            }
        }
        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }
        }
    }
    if (!modified[0]) u = n - qy;                               //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

    return u + d + l + r + ul + ur + dl + dr;
}

int main() {

    int n, k, qx, qy;
    cin >> n >> k >> qy >> qx;
    const int c = k;
    vector<vector<int>> ob(k);
    for (int i = 0; i < k; i++) {
        ob[i].resize(2);
        cin >> ob[i][0] >> ob[i][1];
    }

    cout << queensAttack(n,k,qy,qx,ob);

    return 0;
}

Engelleri aştığımı unuttum ve dizideki engeller en yakından en uzağa doğru sıralanmadığı için yalnızca yeni mesafe daha küçükse mevcut mesafeyi değiştirir.

İyileştirme için bazı geri bildirim veya öneriler alabilir miyim? Teşekkürler!

Answer 1

Genel gözlemler

Hacker Rank tarafından sağlanan catchall başlığını kullanmak yerine gerekli başlıkları eklemeniz iyi oldu. Gereksiz başlıkları dahil ettiniz, kod cmathveya olmadan derlenir algorithm. Yalnızca kodu derlemek için gerekli olanı ekleyin. Gereksiz üstbilgilerin kullanılması derleme sürelerini artırabilir çünkü C ++ aslında geçici bir dosya oluşturur ve üstbilgileri bu geçici dosyaya kopyalar.

Profesyonel bir yazılım geliştiricisi olarak, kodun bakımı (özelliklerin eklenmesi, hataların giderilmesi) ile ilgilenilmesi gerekir. Kod yazabilirsiniz ama onu koruyan kişi olmayabilirsiniz çünkü tatilde olabilirsiniz, başka bir şirkette daha iyi bir iş bulmuş olabilirsiniz, aniden zengin olabilirsiniz.

Bu kodun bakımı çok zor olacak. Bazılarının okunması çok kolay, bir kısmı ise neredeyse okunamaz durumda. Neredeyse okunamayan kodların bazı örnekleri şunlardır:

    int u, d, l, r, ul, ur, dl, dr;                 //up, down, left, right, up-left, up-right, down-left, down-right
    u = d = l = r = ul = ur = dl = dr = 0;

ve

    if (!modified[0]) u = n - qy;        //if they never been modified means no obstacles in path so use calculate distance from edge to queen (probably better way to do this)
    if (!modified[1]) d = qy - 1;
    if (!modified[2]) l = qx - 1;
    if (!modified[3]) r = n - qx;
    if (!modified[4] && qy != n && qx != 1) ul = (qx - 1 < n - qy) ? qx - 1 : n - qy;
    if (!modified[5] && qy != n && qx != n) ur = (n - qx < n - qy) ? n - qx : n - qy;
    if (!modified[6] && qy != 1 && qx != 1) dl = (qx - 1 < qy - 1) ? qx - 1 : qy - 1;
    if (!modified[7] && qy != 1 && qx != n) dr = (n - qx < qy - 1) ? n - qx : qy - 1;

İşlev queensAttack()88 satırdır ve boyutu yazmak, okumak, hata ayıklamak veya sürdürmek çok zor olan tek bir işlevdir.

Önlemek using namespace std;

Profesyonel olarak kodlama yapıyorsanız, muhtemelen using namespace std;ifadeyi kullanma alışkanlığından kurtulmalısınız . Kod, cout( std::cin, std::cout) nereden ve diğer tanımlayıcıların nereden geldiğini daha net bir şekilde tanımlayacaktır . Kodunuzda ad alanlarını kullanmaya başladığınızda, her işlevin nereden geldiğini belirlemek daha iyidir, çünkü farklı ad alanlarından işlev adı çakışmaları olabilir. coutKendi sınıflarınız içinde geçersiz kılabileceğiniz tanımlayıcı ve kendi sınıflarınızda da operatörü geçersiz kılabilirsiniz <<. Bu yığın taşma sorusu bunu daha ayrıntılı olarak tartışır.

Karmaşıklık

İşlev queensAttack()çok karmaşık (çok fazla yapıyor). İşlevlere bölünmeli, en az 3 olası işlev ve muhtemelen daha fazlasını görüyorum. İyi bir tasarım tekniği, her problemin çözülmesi çok kolay olana kadar bir problemi daha küçük problemlere ayırmaya devam etmektir. Bu aynı zamanda kodu daha bakımlı hale getirir.

Burada geçerli olan Tek Sorumluluk İlkesi adı verilen bir programlama ilkesi de vardır. Tek Sorumluluk Prensibi durumları:

her modülün, sınıfın veya işlevin, yazılım tarafından sağlanan işlevselliğin tek bir parçası üzerinde sorumluluğu olması ve bu sorumluluğun tamamen bu modül, sınıf veya işlev tarafından kapsanması gerektiği.

Sihirli Sayılar

İşlevde queensAttack()(0'dan 7'ye kadar) Sihirli Sayılar vardır , kodu daha okunabilir ve bakımı daha kolay hale getirmek için sembolik sabitler oluşturmak daha iyi olabilir, bu durumda bir enum da kullanılabilir. Bu numaralar pek çok yerde kullanılabilir ve sadece bir satırda düzenleme yapılarak değiştirilebilmesi bakımı kolaylaştırır.

Koddaki sayısal sabitlere bazen Sihirli Sayılar denir , çünkü onlar için açık bir anlam yoktur. Stackoverflow'da bununla ilgili bir tartışma var .

unsignedDizin Değişkenleri için Türleri Tam Sayıya Tercih Et

Dizilere veya diğer kap türlerine dizin oluştururken, size_ttamsayılar yerine işaretsiz türleri kullanmak daha iyidir. İmzalanmamış türler negatif olamaz ve negatif bir dizin kullanmak tanımsız davranışlara yol açabilir. size()Tüm konteyner tipi döner fonksiyonu size_tve kod döngü için bir tür uyumsuzluğu uyarının üretilmesi edilir:

    for (int i = 0; i < obstacles.size(); i++) {    //loop through all obstacles, if it is in path get distance to queen

Değişken Beyanlar

Her satıra bir değişken bildirin ve ilklendirin. Aşağıdakiler çok fazla ek dikey alanla sonuçlanırken, okunması ve bakımı daha kolaydır:

    int u = 0;
    int d = 0;
    int l = 0;
    int r = 0;
    int ul = 0;
    int ur = 0;
    int dl = 0;
    int dr = 0;
    bool modified[8] = { false };

Bazılarının bir değişken eklemesi veya silmesi gerekiyorsa, mevcut kodu değiştirmekten çok bir satır eklemek veya bir satırı silmek çok daha kolaydır. Bu durumda, özellikle yukarıda bahsedilen enum her iki diziyi de indekslemek için kullanılıyorsa, halihazırda var olan modifikasyonlar dizisiyle eşleşen bir yön dizisine sahip olmak da mümkün olabilir.

Değişken İsimler

Kodu daha okunaklı hale getirmek için açıklayıcı değişken adları kullanmak genellikle daha iyidir. Yorumlar uygundur, ancak bunların da korunması gerekir, kendi kendini belgeleyen kod, yapılabildiğinde yorum kullanmaktan daha iyidir.

KURU Kodu

Bazen KURU kod olarak da anılan Kendini Tekrar Etme İlkesi adlı bir programlama ilkesi vardır . Kendinizi aynı kodu birden çok kez tekrarlarken bulursanız, onu bir işlevde kapsüllemek daha iyidir. Yinelemeyi de azaltabilecek kodda döngü yapmak mümkünse.

Bu çok tekrar eden bir koddur:

        if (abs(qy - obstacles[i][0]) == abs(qx - obstacles[i][1])) {   //diagonals, checking if it is on the diagonal path of the queen
            if (obstacles[i][0] > qy && obstacles[i][1] < qx) {         //check if it is top left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[4] && ul > temp || !modified[4]) {
                    ul = temp;
                }
                modified[4] = true;
            }
            if (obstacles[i][0] > qy && obstacles[i][1] > qx) {         //check if it is top right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[5] && ur > temp || !modified[5]) {
                    ur = temp;
                }
                modified[5] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] < qx) {         //check if it is bottom left diagonal
                temp = qx - obstacles[i][1] - 1;
                if (modified[6] && dl > temp || !modified[6]) {
                    dl = temp;
                }
                modified[6] = true;
            }
            if (obstacles[i][0] < qy && obstacles[i][1] > qx) {         //check if it is bottom right diagonal
                temp = obstacles[i][1] - qx - 1;
                if (modified[7] && dr > temp || !modified[7]) {
                    dr = temp;
                }
                modified[7] = true;
            }

Answer 2

Senin kodun:

1. Yalnızca ihtiyacınız olduğunu düşündüğünüz başlıkları eklemeniz çok güzel. Sen bir şey kullanmayın <cmath>veya <algorithm>gerçi.

2. using namespace std;açıkça kötüdür. Bu ad alanı dahil edilmek üzere tasarlanmamıştır, bu nedenle içeriklerinin kapsamlı, sabit ve güvenilir bir listesi yoktur.
   " Neden" ad alanı std kullanıyor "konusuna bakın . ayrıntılar için kötü bir uygulama olarak kabul edilir mi? "

3. Küçük önemsiz türler, değere göre kopyalamadan daha iyidir. Daha az dolaylı erişim, daha verimli erişim anlamına gelir ve değerle uğraşan başka kimselerden sakınmaya gerek kalmaz, bu da kod hakkında akıl yürütmeyi geliştirir ve genellikle daha iyi optimizasyona olanak tanır.
   Bkz. " C ++ 'da, neden tüm fonksiyon parametreleri referans olmamalı? ".

4. std::spanBitişik nesnelerin bir görünümünü geçirmek için bir göz atın .
   Ayrıca bkz. " " Aralık "nedir ve ne zaman kullanmalıyım? ".

5. C ++, C ++ 11'den beri aralık döngüleri içerir. Endeksler veya yineleyicilerle manuel olarak uğraşmaktan çok daha az hata eğilimi.

6. Bir ışının bir engelle karşılaşıp karşılaşmadığını kontrol etmek için bayrakların kullanılması ve aksi takdirde maksimum değeri geri döndürmek belirgin bir şekilde yetersizdir. Sadece maksimum ile başlatın ve gerektiği gibi güncelleyin.

7. std::vectorİki uzunluklu A , bir noktanın koordinatlarını saklamak için çok zayıf bir veri yapısıdır. Çok verimsiz, elverişsiz ve hataya meyillidir. Önemsiz bir özel tür için tek bir satır yatırmayı reddederseniz , en azından bir std::pair, std::arrayveya kullanın std::tuple.

8. Kodunuz hiçbir zaman kullanıcı girişinin iyi biçimlendirildiğini test etmez. Aslında, böyle bir meydan okuma için bu haklı olabilir, o yüzden devam edelim.

9. return 0;örtülü olduğu main()C ++ ve C99 + içinde.

Yaklaşımınız optimize edilebilir ve daha da basitleştirilebilir:

1. Kraliçe merkezli bir koordinat sistemi kullanın. Tüm kontroller kraliçe ile ilgili ve şimdi çok daha basit.

2. Kraliçenin saldırısının her bir kolunun erişimini bildiğiniz engelleri göz önünde bulundurarak saklarsanız (sınır ile başlatırsanız), işlemden sonra her engeli hemen düşürebilirsiniz.

#include <algorithm>
#include <iostream>

int main() {
    int x, y, k, qx, qy;
    std::cin >> x >> k >> qx >> qy;

    int d = qy,
        l = qx,
        u = x + 1 - qy,
        r = x + 1 - qx;
    int dl = std::min(d, l),
        dr = std::min(d, r),
        ul = std::min(u, l),
        ur = std::min(u, r);
    auto update = [](int a, int& b, int& c){
        if (a < 0)
            b = std::min(b, -a);
        else
            c = std::min(c, a);
    };

    while (k--) {
        std::cin >> x >> y;
        x -= qx;
        y -= qy;
        if (!x)
            update(y, d, u);
        else if (!y)
            update(x, l, r);
        else if (x == y)
            update(x, dl, ur);
        else if (x == -y)
            update(x, ul, dr);
    }

    std::cout << (d + u + l + r + dl + dr + ul + ur - 8);
}

Dikkat: Yukarıdaki kodun doğru olduğu kanıtlanmıştır, asla çalıştırılmamalıdır.