Queen's Attack II di Hackerrank

Oct 27 2020

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

Una regina è in piedi su una scacchiera nxn. Le righe della scacchiera sono numerate da 1 a n, dal basso verso l'alto; le sue colonne sono numerate da 1 a n, andando da sinistra a destra. Ogni quadrato sulla scacchiera è indicato da una tupla, (r, c), che descrive la riga, r, e la colonna, c, dove si trova il quadrato.

La regina è in posizione (rq, cq) e, con una sola mossa, può attaccare qualsiasi casella in una qualsiasi delle otto direzioni (sinistra, destra, su, giù o le quattro diagonali). Nel diagramma sottostante, i cerchi verdi indicano tutte le celle da cui la regina può attaccare (4,4):

Ci sono \$k\$ostacoli sulla scacchiera che impediscono alla regina di attaccare qualsiasi casella che abbia un ostacolo che blocca il percorso della regina verso di essa. Ad esempio, un ostacolo nella posizione \$(3,5)\$nel diagramma sopra impedirebbe alla regina di attaccare le cellule \$(3,5)\$, \$(2,6)\$e \$(1,7)\$:

Data la posizione della regina e l'ubicazione di tutti gli ostacoli, trova e stampa il numero di quadrati che la regina può attaccare dalla sua posizione in \$(r_q,c_q)\$.

Formato di input

La prima riga contiene due interi separati da spazi che descrivono i rispettivi valori di \$n\$(la lunghezza del lato della tavola) e \$k\$ (il numero di ostacoli).

La riga successiva contiene due interi separati da spazi che descrivono i rispettivi valori di \$r_q\$e \$c_q\$, che denota la posizione della regina.

Ogni riga \$i\$della \$k\$le righe successive contengono due interi separati da spazi che descrivono i rispettivi valori \$r_i\$di \$c_i\$e, indicando la posizione dell'ostacolo \$i\$.

Vincoli

\$ 0 \leq n \leq 100000\$

\$ 0 \leq k \leq 100000\$

Una singola cella può contenere più di un ostacolo; tuttavia, è garantito che non ci sarà mai un ostacolo in posizione \$(r_q,c_q)\$ dove si trova la regina.

Formato di output

Stampa il numero di caselle che la regina può attaccare dalla posizione.

Ingresso campione 0

\$4\$ \$0\$

\$4\$ \$4\$

Output di esempio 0

\$9\$

Spiegazione 0

La regina è in posizione \$(4,4)\$su un \$4\$x \$4\$ scacchiera senza ostacoli:

Quindi stampiamo il numero di quadrati che può attaccare da quella posizione, che è \$9\$.

Il mio approccio:

Invece di iterare attraverso ogni singolo punto nel percorso delle regine poiché sarà un uso intensivo di risorse quando n è molto alto, sono andato separando i percorsi in 8 direzioni diverse (in alto a sinistra, in alto, in alto a destra, a destra, ecc.).

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

Poi ho controllato se c'è un ostacolo nel percorso controllando se le regine x = ostacoli x o regine y = ostacoli y e se si trova sul percorso verticale / orizzontale delle regine avrei trovato la distanza calcolando il delta - 1 e per trovare i punti diagonali che conosco poiché i punti devono avere una pendenza 1 o -1 per essere nel percorso delle regine, quindi ho controllato se | queen's y - ostacolo è y | = | x della regina - x dell'ostacolo | e se è vero che trovo il delta tra x o y come entrambi funzionano e se non ci sono ostacoli userei solo il bordo per trovare la distanza. Controllo solo per vedere se l'ostacolo era nel percorso, quindi calcolo i possibili punti quindi segna la direzione come risolta, quindi se non è contrassegnato significa che non ci sono ostacoli nel percorso, quindi trovo la distanza dal bordo usando:

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;

Ci scusiamo per lo stile disordinato, questa è la mia prima volta su stackoverflow / stackexchange.

Codice completo:

#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;
}

Ho dimenticato di menzionare che percorro gli ostacoli e sostituisco la distanza corrente solo se quella nuova è più piccola poiché gli ostacoli nella matrice non sono in ordine dal più vicino al più lontano.

Posso ricevere feedback o suggerimenti per il miglioramento? Grazie!

Risposte

5 pacmaninbw Oct 28 2020 at 07:19

Osservazioni generali

È stato positivo che tu abbia incluso le intestazioni necessarie anziché utilizzare l'intestazione catchall fornita da Hacker Rank. Hai incluso intestazioni non necessarie, il codice viene compilato senza cmatho algorithm. Includere solo ciò che è necessario per compilare il codice. L'utilizzo di intestazioni non necessarie può aumentare i tempi di compilazione perché C ++ crea effettivamente un file temporaneo e copia le intestazioni in quel file temporaneo.

In qualità di sviluppatore di software professionale, è necessario preoccuparsi della manutenzione del codice (aggiunta di funzionalità, correzione di bug). Puoi scrivere codice ma non essere la persona che lo mantiene perché potresti essere in vacanza, potresti aver ottenuto un lavoro migliore in un'altra azienda, potresti essere diventato improvvisamente ricco.

Questo codice sarà molto difficile da mantenere. Alcuni sono molto facili da leggere e altri sono quasi illeggibili. Alcuni esempi di codice quasi illeggibile sono:

    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;

    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;

La funzione queensAttack()è di 88 righe e una singola funzione di quella dimensione è molto difficile da scrivere, leggere, eseguire il debug o mantenere.

Evitare `using namespace std;`

Se stai codificando in modo professionale, probabilmente dovresti perdere l'abitudine di usare l' using namespace std;istruzione. Il codice definirà più chiaramente la coutprovenienza e gli altri identificatori ( std::cin, std::cout). Quando inizi a utilizzare gli spazi dei nomi nel codice, è meglio identificare la provenienza di ciascuna funzione perché potrebbero esserci conflitti di nomi di funzioni da diversi spazi dei nomi. L'identificatore coutche puoi sovrascrivere all'interno delle tue classi e puoi sovrascrivere l'operatore anche <<nelle tue classi. Questa domanda sull'overflow dello stack discute questo in modo più dettagliato.

Complessità

La funzione queensAttack()è troppo complessa (fa troppo). Dovrebbe essere suddiviso in funzioni, vedo almeno 3 possibili funzioni e probabilmente di più. Una buona tecnica di progettazione consiste nel suddividere un problema in problemi più piccoli separati finché ogni problema non è molto facile da risolvere. Questo rende anche il codice più manutenibile.

C'è anche un principio di programmazione chiamato Principio di responsabilità unica che si applica qui. Il principio di responsabilità unica afferma:

che ogni modulo, classe o funzione dovrebbe avere la responsabilità su una singola parte della funzionalità fornita dal software e tale responsabilità dovrebbe essere interamente incapsulata da quel modulo, classe o funzione.

Numeri magici

Ci sono numeri magici nella queensAttack()funzione (da 0 a 7), potrebbe essere meglio creare costanti simboliche per rendere il codice più leggibile e più facile da mantenere, in questo caso potrebbe essere utilizzata anche un'enumerazione. Questi numeri possono essere usati in molti posti e la possibilità di cambiarli modificando solo una riga rende più facile la manutenzione.

Le costanti numeriche nel codice sono a volte indicate come numeri magici , perché non hanno un significato ovvio per loro. C'è una discussione su questo su stackoverflow .

Preferisci i `unsigned`tipi a Integer per le variabili indice

Quando si indicizza in matrici o altri tipi di contenitori è meglio usare tipi senza segno come size_tpiuttosto che interi. I tipi senza segno non possono diventare negativi e l'utilizzo di un indice negativo può portare a un comportamento indefinito. La size()funzione di tutti i tipi di contenitore restituisce size_te il codice genera un avviso di mancata corrispondenza del tipo nel ciclo for:

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

Dichiarazioni di variabili

Dichiarare e inizializzare le variabili una per riga. Sebbene i seguenti risultati in molto spazio verticale aggiunto, sono più facili da leggere e mantenere:

    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 };

Se alcuni hanno bisogno di aggiungere o eliminare una variabile, è molto più semplice aggiungere una riga o eliminare una riga che modificare il codice corrente. In questo caso potrebbe anche essere possibile avere una matrice di direzioni che corrisponde alla matrice di modifiche già esistente, soprattutto se l'enumerazione menzionata sopra viene utilizzata per indicizzare entrambi gli array.

Nomi variabili

In genere è meglio utilizzare nomi di variabili descrittivi per rendere il codice più leggibile. I commenti vanno bene, ma devono anche essere mantenuti, il codice auto documentante è meglio che usare i commenti quando ciò può essere fatto.

Codice ASCIUTTO

Esiste un principio di programmazione chiamato principio Don't Repeat Yourself a volte indicato come codice DRY. Se ti ritrovi a ripetere lo stesso codice più volte è meglio incapsularlo in una funzione. Se è possibile eseguire il ciclo del codice, è possibile ridurre anche la ripetizione.