Kingdom Defence Problem Using C++

Filed Under: C++
Kingdom Defence Problem Using C

Today, we’ll learn to solve the kingdom defense problem using C++. It is a very popular problem from SPOJ(Sphere Online Judge). This problem also goes by the name DEFKIN. This has already been asked about during many coding competitions. We’ll learn to solve this problem most efficiently. Let’s go through the problem statement.

Also read: Chopsticks Pairing Problem Using C++

Problem Statement

A new strategy game Kingdom Defence is trending among the youth. There are a certain number of rectangular cells that represents a kingdom. There are some watchtowers built at different locations throughout the kingdom. These guard towers ensure the safety of the people living in the kingdom. However, a guard tower can only defend the row and the column in which it lies. Your task is to find out the number of cells in the largest rectangle that is unguarded.

Input Format

The input will be of the form:

R, C, N
r1, c1
r2, c2
.........
.
.
.
rn, cn

Where R, C, and N represent the rows, columns, and number of watchtowers of the kingdom respectively. And the following N lines represent the location of each watchtower.

For example,

Input:
15 8 3
3 8
11 2
8 6

Answer: 12

Input:
3 4 1
1 1

Answer: 6

Input:
5 5 2
1 1
5 5

Answer: 9

Approach

Key To Solving This Problem

We have to find the largest undefended area.

  • area = dx * dy
  • Here, dx represents the row-wise distance between two watchtowers.
  • And, dy represents the column-wise distance between two watchtowers.
  • max_area = max(dx) * max(dy)

So, our greedy choice will be to find the largest value of dx and dy.

Pseudocode

Below is the step-by-step process that we’ll follow to implement the algorithm.

  • Sort the values of the x-coordinates and y-coordinates of the locations of the towers.
  • Initialize dx and dy as:
    • dx = x_coordinate[0];
    • dy = y_coordinate[0];
  • Iterate over the sorted coordinates.
    • dx = x_coordinate[i – 1] – x_coordinate[i];
    • dy = y_coordinate[i – 1] – y_coordinate[i];
    • During each iteration, check if there’s a larger value of dx and dy.
      • max_dx = max(dx, max_dx);
      • max_dy = max(dx, max_dy);
  • Finally, evaluate the area as:
    • max_area = max_dx * max_dy;

Kingdom Defence Problem Using C++ Program

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

using namespace std;

int kingdom_defence(vector <int> x_coordinate, vector <int> y_coordinate, int R, int C, int N)
{
        // first sort the vectors according the their
        // x and y coordinates
        sort(x_coordinate.begin(), x_coordinate.end());
        sort(y_coordinate.begin(), y_coordinate.end());

        // initialize the values of dx and dy
        int dx = x_coordinate[0];
        int dy = y_coordinate[0];
        int max_dx = dx;
        int max_dy = dy;

        // iterate over the sorted vectors
        for(int i = 1; i < N; i++)
        {
                // evaluate the values of dx and dy
                dx = x_coordinate[i] - x_coordinate[i - 1] - 1;
                dy = y_coordinate[i] - y_coordinate[i - 1] - 1;

                max_dx = max(max_dx, dx);
                max_dy = max(max_dy, dy);
        }

        // corner case:
        // check for the ends
        max_dx = max(max_dx, R - x_coordinate[N - 1]);
        max_dy = max(max_dy, C - y_coordinate[N - 1]);

        int max_area = max_dx * max_dy;

        return max_area;
}

int main()
{
        cout << "Enter the value of rows, columns and the number of watchtowers" << endl;
        int R, C, N;
        cin >> R >> C >> N;

        vector <int> x_coordinate(N);
        vector <int> y_coordinate(N);

        cout << "Enter the values of the locations of the watchtowers" << endl;

        for(int i = 0; i < N; i++)
        {
                int r, c;
                cin >> r >> c;

                x_coordinate[i] = r;
                y_coordinate[i] = c;
        }

        cout << "The number of cells in the largest unguarded area are: " << kingdom_defence(x_coordinate, y_coordinate, R, C, N) << endl;

        return 0;
}
Kingdom Defence Code
Kingdom Defence Code

Output

Kingdom Defence Output
Kingdom Defence Output

Conclusion

In this article, we learned to solve the kingdom defence problem using C++. We used the STL(Standard Template Library) sort function to make use of our greedy choice. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/58999/bucket-sort-cpp

https://www.journaldev.com/59494/ladder-problem-using-recursion-cpp

close
Generic selectors
Exact matches only
Search in title
Search in content
Post Type Selectors