How many squares can M bishops cannot go in an N*N chess board?

Question

I am currently working on a program that calculates moves of an M amount of bishops on an N*N size chess grid. I have a program to find only the unaccessible squares for one bishop. Can anybody help me with this?

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

If bishop's row and column is both 4 and the grid size is 8*8, then that bishop has 51 squares that it can't visit. But I can't figure out how I should approach this.

Answer 1

There are several ways to achieve this task but I'll give you a simple algorithm.

Number of squares those bishops cannot visit =

Total number of squares - Number of squares those bishops can visit

Since it's easy to calculate the total number of squares (n * n), the problem boils down to calculating the total number of squares that can be visited by those bishops from their given position.

In your code, you do not read the number of bishops and their initial coordinates. That should be the first step.

Since you are working in C++, you can use an std::set of std::pair to simplify your task. A set is used to store unique elements, so you can use that to store the locations that can be visited by the bishops and avoid duplicates. A pair can be used to store the location as coordinates (i, j).

Iterate through each bishop and calculate the squares they could visit and add it to the set. In the end, you have the total number of squares that the bishops can cover as the size of that set.

Then use the above formula to get your desired result.

Below is an implementation of that approach:

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