Сколько квадратов могут не иметь M епископы go на N * N шахматной доске?

Question

В настоящее время я работаю над программой, которая вычисляет ходы M слонов на шахматной сетке размера N * N. У меня есть программа, чтобы найти только недоступные квадраты для одного епископа. Кто-нибудь может мне помочь с этим?

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int ways(int r,int c,int n)
{
    int TL,TR,BL,BR;
    TL = min(r,c) - 1;
    TR = min(r,(n+1)-c) - 1;
    BL = n - max(r,(n+1)-c);
    BR = n - max(r,c);
    return (TL+TR+BL+BR);
}

int main()
{
    int r,c,n;
    cin >> r >> c >> n;
    cout << n*n - ways(r,c,n);
    return 0;
}

Если строка и столбец слона равны 4, а размер сетки 8 * 8, то у этого слона 51 клетка, которую он не может посетить. Но я не могу понять, как мне к этому подойти.

Answer 1

Есть несколько способов решения этой задачи, но я дам вам простой алгоритм.

Количество квадратов, которые эти слоны не могут посетить =

Всего количество квадратов - Количество квадратов, которые эти епископы могут посетить

Поскольку общее количество квадратов легко вычислить ( n * n ), проблема сводится к вычислению общего числа квадратов, которые могут посетить эти епископы с их заданной позиции.

В вашем коде вы не читаете число епископов и их начальные координаты. Это должен быть первый шаг.

Поскольку вы работаете в C ++, вы можете использовать std::set из std::pair, чтобы упростить вашу задачу. Набор используется для хранения уникальных элементов, поэтому вы можете использовать его для хранения мест, которые могут посетить епископы, и избежать дублирования. Пара может использоваться для сохранения местоположения в виде координат (i, j) .

Перебирать каждого слона, вычислять квадраты, которые они могут посетить, и добавлять его в набор. В итоге у вас есть общее количество квадратов, которые епископы могут покрыть как размер этого набора.

Затем используйте приведенную выше формулу, чтобы получить желаемый результат.

Ниже является реализацией этого подхода:

#include <iostream>
#include <set>
#include <utility>

using namespace std;

int main()
{
    int n; // Size of the chess board
    int m; // Number of bishops
    int x, y; // Initial location of a bishop
    int i, j; // Coordinates for iteration

    // Read the limits
    cin >> n >> m;
    if (n < 0) n = 0;

    // Read the location of the bishops
    set<pair<int, int>> bishops;
    for (i = 0; i < m; ++i)
    {
        cin >> x >> y;
        if (x >= 0 && x < n && y >= 0 && y < n)
            bishops.insert({x, y});
    }

    // This is the key
    set<pair<int, int>> visitableLocations;

    // Calculate the squares that could be visited by all the bishops
    for (const auto& bishop : bishops)
    {
        x = bishop.first;
        y = bishop.second;
        /*
        You don't need this after the edit made to your post
        Because you don't consider its initial square as visitable
        // Add the original location of the bishop
        if (x >= 0 && x < n && y >= 0 && y < n)
            visitableLocations.insert({x, y});
        */

        // Check all the diagonal directions
        // Within the boundaries of the board
        // No other bishop should block the way

        // auto debug = [&](){cout << i << ' ' << j << '\n';};

        // north-east
        i = x; j = y;
        while (++i < n && ++j < n)
            if (bishops.find({i, j}) == bishops.end())
                visitableLocations.insert({i, j});//debug();}

        // north-west
        i = x; j = y;
        while (--i >= 0 && ++j < n)
            if (bishops.find({i, j}) == bishops.end())
                visitableLocations.insert({i, j});//debug();}

        // south-east
        i = x; j = y;
        while (++i < n && --j >= 0)
            if (bishops.find({i, j}) == bishops.end())
                visitableLocations.insert({i, j});//debug();}

        // south-west
        i = x; j = y;
        while (--i >= 0 && --j >=0)
            if (bishops.find({i, j}) == bishops.end())
                visitableLocations.insert({i, j});//debug();}
    }

    // Now get the final answer
    int ans = (n * n) - visitableLocations.size();
    cout << ans;

    return 0;
}