Hackerrank's Queen's Attack II

Oct 27 2020

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

Uma rainha está de pé em um tabuleiro de xadrez nxn. As linhas do tabuleiro de xadrez são numeradas de 1 an, indo de baixo para cima; suas colunas são numeradas de 1 an, indo da esquerda para a direita. Cada quadrado no tabuleiro é denotado por uma tupla, (r, c), que descreve a linha, r, e a coluna, c, onde o quadrado está localizado.

A rainha está na posição (rq, cq) e, em um único movimento, ela pode atacar qualquer casa em qualquer uma das oito direções (esquerda, direita, cima, baixo ou nas quatro diagonais). No diagrama abaixo, os círculos verdes denotam todas as células a partir das quais a rainha pode atacar (4,4):

Existem \$k\$obstáculos no tabuleiro de xadrez que impedem a rainha de atacar qualquer casa que tenha um obstáculo bloqueando o caminho da rainha até ela. Por exemplo, um obstáculo no local \$(3,5)\$no diagrama acima evitaria que a rainha atacasse as células \$(3,5)\$, \$(2,6)\$, e \$(1,7)\$:

Dada a posição da rainha e a localização de todos os obstáculos, encontre e imprima o número de casas que a rainha pode atacar de sua posição em \$(r_q,c_q)\$.

Formato de entrada

A primeira linha contém dois inteiros separados por espaço que descrevem os respectivos valores de \$n\$(o comprimento lateral da placa) e \$k\$ (o número de obstáculos).

A próxima linha contém dois inteiros separados por espaço que descrevem os respectivos valores de \$r_q\$e \$c_q\$, denotando a posição da rainha.

Cada linha \$i\$da \$k\$as linhas subsequentes contêm dois inteiros separados por espaço que descrevem os respectivos valores \$r_i\$de \$c_i\$e, denotando a posição do obstáculo \$i\$.

Restrições

\$ 0 \leq n \leq 100000\$

\$ 0 \leq k \leq 100000\$

Uma única célula pode conter mais de um obstáculo; no entanto, é garantido que nunca haverá um obstáculo na posição \$(r_q,c_q)\$ onde a rainha está localizada.

Formato de saída

Imprime o número de quadrados que a rainha pode atacar da posição.

Amostra de entrada 0

\$4\$ \$0\$

\$4\$ \$4\$

Saída de amostra 0

\$9\$

Explicação 0

A rainha está em posição \$(4,4)\$em um \$4\$x \$4\$ tabuleiro de xadrez sem obstáculos:

Em seguida, imprimimos o número de quadrados que ela pode atacar daquela posição, que é \$9\$.

Minha abordagem:

Em vez de iterar por todos os pontos no caminho das rainhas, pois isso consumirá muitos recursos quando n for muito alto, comecei a separar os caminhos em 8 direções diferentes (acima à esquerda, acima, à direita, à direita, etc).

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

Então eu verifiquei se há algum obstáculo no caminho verificando se as rainhas x = obstáculos x ou rainhas y = obstáculos y e se está no caminho vertical / horizontal das rainhas eu encontraria a distância calculando o delta - 1 e para encontrar os pontos diagonais eu sei, já que os pontos devem ter uma inclinação de 1 ou -1 para estar no caminho das rainhas, então eu verifiquei se | dama é y - obstáculo é | = | x da rainha - x do obstáculo | e se for verdade, então encontro o delta entre ox ou y como ambos funcionam e se não houver obstáculos, eu apenas usaria a aresta para encontrar a distância. Eu apenas verifico se o obstáculo estava no caminho, então calculo os pontos possíveis e então marque a direção como resolvida, então se não estiver marcada significa que não há obstáculos no caminho, então eu acho a distância da borda 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;

Desculpe pelo estilo confuso, esta é minha primeira vez em stackoverflow / stackexchange.

Código 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;
}

Esqueci de mencionar que eu faço um loop pelos obstáculos e só substituo a distância atual se a nova for menor, pois os obstáculos na matriz não estão em ordem do mais próximo para o mais distante.

Posso obter algum feedback ou sugestões para melhorias? Obrigado!

Respostas

5 pacmaninbw Oct 28 2020 at 07:19

Observações gerais

Foi bom ter incluído os cabeçalhos necessários em vez de usar o cabeçalho genérico fornecido pelo Hacker Rank. Você incluiu cabeçalhos desnecessários, o código é compilado sem cmathou algorithm. Inclua apenas o necessário para fazer a compilação do código. O uso de cabeçalhos desnecessários pode aumentar o tempo de construção porque o C ++ na verdade cria um arquivo temporário e copia os cabeçalhos nesse arquivo temporário.

Como desenvolvedor de software profissional, é preciso se preocupar com a manutenção do código (adicionar recursos, corrigir bugs). Você pode escrever código, mas não ser a pessoa que o mantém, porque pode estar de férias, pode ter conseguido um emprego melhor em outra empresa, pode ter ficado rico de repente.

Este código será muito difícil de manter. Algumas são muito fáceis de ler e outras quase ilegíveis. Alguns exemplos de código quase ilegível são:

    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;

A função queensAttack()tem 88 linhas e uma única função cujo tamanho é muito difícil de escrever, ler, depurar ou manter.

Evitar `using namespace std;`

Se você está programando profissionalmente, provavelmente deve abandonar o hábito de usar a using namespace std;instrução. O código definirá mais claramente de onde coute outros identificadores estão vindo ( std::cin, std::cout). À medida que você começa a usar namespaces em seu código, é melhor identificar de onde vem cada função, porque pode haver conflitos de nomes de função de diferentes namespaces. O identificador que coutvocê pode substituir em suas próprias classes e também pode substituir o operador <<em suas próprias classes. Esta questão de estouro de pilha discute isso com mais detalhes.

Complexidade

A função queensAttack()é muito complexa (faz muito). Deve ser dividido em funções, vejo pelo menos 3 funções possíveis e provavelmente mais. Uma boa técnica de projeto é continuar dividindo um problema em problemas menores separados até que cada problema seja muito fácil de resolver. Isso também torna o código mais sustentável.

Também existe um princípio de programação denominado Princípio de Responsabilidade Única que se aplica aqui. O Princípio de Responsabilidade Única afirma:

que cada módulo, classe ou função deve ter responsabilidade sobre uma única parte da funcionalidade fornecida pelo software, e essa responsabilidade deve ser totalmente encapsulada por esse módulo, classe ou função.

Números mágicos

Existem números mágicos na queensAttack()função (0 a 7), pode ser melhor criar constantes simbólicas para eles para tornar o código mais legível e fácil de manter; neste caso, um enum também pode ser usado. Esses números podem ser usados em muitos lugares e ser capaz de alterá-los editando apenas uma linha torna a manutenção mais fácil.

As constantes numéricas no código às vezes são chamadas de números mágicos , porque não há um significado óbvio para elas. Há uma discussão sobre isso no stackoverflow .

Preferir `unsigned`tipos a inteiros para variáveis de índice

Ao indexar em matrizes ou outros tipos de contêiner, é melhor usar tipos não assinados, como em size_tvez de inteiros. Tipos não assinados não podem se tornar negativos e usar um índice negativo pode levar a um comportamento indefinido. A size()função de todos os tipos de contêiner retorna size_te o código está gerando um aviso de incompatibilidade de tipo no loop for:

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

Declarações de variáveis

Declare e inicialize as variáveis uma por linha. Embora o seguinte resulte em muito espaço vertical adicionado, é mais fácil de ler e manter:

    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 alguém precisar adicionar ou excluir uma variável, é muito mais fácil adicionar ou excluir uma linha do que modificar o código atual. Nesse caso, também pode ser possível ter um array de direções que corresponda ao array de modificações já existente, especialmente se o enum mencionado acima for usado para indexar ambos os arrays.

Nomes de Variáveis

Geralmente, é melhor usar nomes de variáveis descritivos para tornar o código mais legível. Os comentários são permitidos, mas também precisam ser mantidos. O código de autodocumentação é melhor do que usar comentários, quando isso pode ser feito.

Código DRY

Existe um princípio de programação denominado Princípio de Don't Repeat Yourself, às vezes referido como código DRY. Se você repetir o mesmo código várias vezes, é melhor encapsulá-lo em uma função. Se for possível percorrer o código, isso pode reduzir a repetição também.