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