What's a good algorithm for Defense of a Kingdom?
I was trying to Solve the Defense of a Kingdom problem and came up with an algorithm but it exceeds the time limit of the problem.
I want to know a good algorithm to solve this within the time limit.
The problem:
Theodore implements a new strategy game “Defense of a Kingdom”. On each level a player defends the Kingdom that is represented by a rectangular grid of cells. The player builds crossbow towers in some cells of the grid. The tower defends all the cells in the same row and the same column. No two towers share a row or a column.
The penalty of the position is the number of cells in the largest undefended rectangle. For example, the position shown on the picture has penalty 12.
Help Theodore w开发者_开发百科rite a program that calculates the penalty of the given position.
Input
The first line of the input file contains the number of test cases.
Each test case consists of a line with three integer numbers: w — width of the grid, h — height of the grid and n — number of crossbow towers (1 ≤ w, h ≤ 40 000; 0 ≤ n ≤ min(w, h)).
Each of the following n lines contains two integer numbers xi and yi — the coordinates of the cell occupied by a tower (1 ≤ xi ≤ w; 1 ≤ yi ≤ h).
Output
For each test case, output a single integer number — the number of cells in the largest rectangle that is not defended by the towers.
Example
Input:
1 15 8 3 3 8 11 2 8 6Output: 12
I would do it like this:
Given w, h as width and height of the playing field, and the coordinates of the towers as (x1,y1) .. (xN,yN), split the coordinates into two lists x1..xN, y1..yN, sort both of those coordinate lists.
Then calculate the empty spaces, e.g. dx[] = { x1, x2-x1, ..., xN - xN-1, (w + 1) - xN }. Do the same for the y coordinates: dy[] = { y1, y2-y1, ..., yN - yN-1, (h + 1) - yN }. Multiply max(dx)-1 by max(dy)-1 and you should have the largest uncovered rectangle. You have to decrement the delta values by one because the line covered by the higher coordinate tower is included in it, but it is not uncovered.
It is easy to see that the set of undefended cells is cartesian product of undefended “holes” in level's walls. So, at first, you don't need to store the whole field in memory — storing just two sequences of towers' coordinates will be enough.
The second observation would be that in final field, with all the towers set up, the largest undefended rectangle is equal to cartesian product of two most wide wall holes. Hence its area is equal to product of the holes' lengths. So what we really need to do is to find two most wide wall holes (one on x axis, one on y), and multiply their lengths. That would be the answer.
The final note is about input. The towers will probably be shuffled in some way around; but we need a way to derive all holes' lengths. This can easily be done by first sorting the coordinate sequences, separately one and the other, and then calculating {xi+1−xi} and {yi+1−yi} in a single pass. In the same pass we can even find the maximums — multiply them, and you are done.
Ok this could be another first idea,
for each defender there is at least 1 and maximum 4 neighbor white area.
- let
a:=0 - for each defender, start from greatest adjacent white area. move from there to an adjacent uncovered space with greater area, that you didn't move there before. do this until there is no possible move.
- if there is no possible move and current area is greater than
astore current area ina.
If you have a 9x6 grid. You have 3 towers.
First calculate the smallest gap for the x axis which has 9 elements. We have 3 towers. 9/3 = 3. So we place one tower per 3 elements.
[ ]
[ ]
[x]
[ ]
[ ]
[x]
[ ]
[ ]
[x]
This is a 2 gap max. We can work this about by diving remaining spaces (6) by number of towers (3). 6/3 = 2.
Now to the same for y axis. 6 squares. 3 towers. 6/3 = one tower per 2 squares:
[ ][x][ ][x][ ][x]
1 space max gap (3/3).
You now have the x and y coordinate of each tower (0 indexed):
1,2
3,5
5,8
The biggest gap is 2x1 = 2.
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][x][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][x][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][x]
I'm 99% sure you can create a general formula for this without the need for loops that returns the x,y pairs of each castle and the biggest penalty area.
EDIT I did notice a small bug in this program: - When I had submitted it originally it was done only for a single test case; I then went back to my IDE to improve the algorithm to work for multiple test cases. After I got it working, I came back here to edit this post and I missed a couple of crucial lines. They are now fixed and I also added some comments of what else could be added to this class if one wants to keep an associated record of each test case along with its corresponding penalty value. End Edit
I encapsulated this into a class. I'm pretty sure there maybe a more elegant way of doing this but this is what I've come up with, using your example of a text file for populating the data structure and the method of returning penalties.
pieces.txt
1
15 8 3
3 8
11 2
8 6
DefenderBoard.h
#ifndef DEFENDER_BOARD_H
#define DEFENDER_BOARD_H
#include <fstream>
#include <vector>
#include <algorithm>
struct Coord {
unsigned x;
unsigned y;
Coord() : x(0), y(0) {}
Coord( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {}
};
class DefenderBoard {
private:
std::string filename;
unsigned testcase;
unsigned gridsize_x;
unsigned gridsize_y;
unsigned numTowers;
std::vector<unsigned> penalties;
std::vector<Coord> cells;
public:
explicit DefenderBoard( const std::string& filenameIn );
~DefenderBoard();
void getPenalties( std::vector<unsigned>& penalties ) const;
private:
void getDataFromFile();
void calculatePenalty();
};
#endif // DEFENDER_BOARD_H
DefenderBoard.cpp
#include "DefenderBoard.h"
DefenderBoard::DefenderBoard( const std::string& filenameIn ) :
filename( filenameIn ),
gridsize_x( 0 ), gridsize_y( 0 ),
testcase( 0 ),
numTowers( 0 ),
penalty( 0 ) {
getDataFromFile();
}
DefenderBoard::~DefenderBoard() {
}
void DefenderBoard::getPenalties( std::vector<unsigned>& penaltiesOut ) const {
penaltiesOut = penalties;
}
void DefenderBoard::getDataFromFile() {
std::ifstream file;
file.open( filename );
if ( !file.is_open() ) {
// Note: This ExceptionHandler will not work for you.
// You will need to supply your own error or exception handling.
std::ostringstream strStream;
strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
throw ExceptionHandler( strStream );
}
file >> testcase;
// Temps
Coord towerCoord;
// t -> testcase | c - tower coords
for ( unsigned t = 0; t < testcase; ++t ) {
file >> gridsize_x;
file >> gridsize_y;
file >> numTowers;
for ( unsigned c = 0; c < numTowers; ++c ) {
file >> towerCoord.x;
file >> towerCoord.y;
cells.push_back( towerCoord );
}
calculatePenalty();
// After Penalty is calculated this test case along with the penalty value
// can be stored into a struct containing both the penalty and a vector of cells
// which would be done here and then that struct would be stored into another container to this class
// If the above is choosen to be done then this needs to be called here instead of within the calculate function
// Clear our cells so it can be reused for each test case found in this file.
cells.clear();
}
file.close();
}
bool compareCoordsX( const struct Coord& a, const struct Coord& b ) {
return a.x > b.x;
}
bool compareCoordsY( const struct Coord& a, const struct Coord& b ) {
return a.y > b.y;
}
void DefenderBoard::calculatePenalty() {
std::vector<unsigned> xValDiff;
std::vector<unsigned> yValDiff;
unsigned diff = 0;
// First Sort By Largest X - Then Find The Differences
std::stable_sort( cells.begin(), cells.end(), compareCoordsX );
unsigned idx = 0;
for ( ; idx < cells.size(); ++idx ) {
// For First Iteration Only
if ( idx == 0 ) {
diff = gridsize_x - cells[idx].x;
xValDiff.push_back( diff );
} else {
diff = cells[idx-1].x - cells[idx].x - 1; // Don't Forget to Subract 1
xValDiff.push_back( diff );
}
}
// Also push back the last value - 1
xValDiff.push_back( cells.back().x - 1 );
// Do Same Thing For Y
std::stable_sort( cells.begin(), cells.end(), compareCoordsY );
idx = 0;
diff = 0;
for ( ; idx < cells.size(); ++idx ) {
// First Iteration Only
if ( idx == 0 ) {
diff = gridsize_y - cells[idx].y;
yValDiff.push_back( diff );
} else {
diff = cells[idx-1].y - cells[idx].y - 1; // Don't Forget to Subtract 1
yValDiff.push_back( diff );
}
}
// Also push back the last value - 1
yValDiff.push_back( cells.back().y - 1 );
unsigned largestX = xValDiff[0];
unsigned largestY = yValDiff[0];
idx = 0;
for ( ; idx < cells.size(); ++idx ) {
if ( xValDiff[idx] > largestX ) {
largestX = xValDiff[idx];
}
if ( yValDiff[idx] > largestY ) {
largestY = yValDiff[idx];
}
}
// Calculate Penalty And Store It
// EDIT - I did update this code after I had originally posted it
// and when I added the update I did forget to change this commented section
// penalty = largestX * largestY;
// It should be like this:
penalties.push_back( largestX * largestY );
// I did have this line of code here too but I moved it out of this function and into the getDataFromFile() method.
// cells.clear();
}
main.cpp
#include <iostream>
#include "DefenderBoard.h"
int main() {
std::vector<unsigned> penalties;
DefenderBoard board( "pieces.txt" );
board.getPenalties( penalties );
unsigned idx = 0;
for ( ; idx < penalties.size(); ++idx ) {
std::cout << penalties[idx] << " ";
}
std::cout << std::endl;
return 0;
}
Output
12
Second Run - Two Test Cases:
pieces.txt
2
15 8 3
3 8
11 2
8 6
12 10 4
2 2
9 7
3 9
8 5
Output
12 8
Note: There is no bounds checking to see if a cell coordinate from the file is greater than the size of the MxN board. So if the grid size is say 8x8 and there is a piece that has a coordinate of [12,2] or [5,9] these will break the algorithm giving you invalid results. I'll leave these error cases as an exercise.
Implementation of Algorithm The idea of this algorithm is to take the size and subtract the farthest piece first. Then you will take that and subtract the next farthest piece from it and subtract 1 until you have reached the last piece, then finally you will take the last piece itself and subtract 1 from it. This will give you all the differences in one direction. Repeat this for the other direction as well. Then you are looking for the largest size in both x and y. Once you have them all you need to do is calculate the product of the largest differences in both the x and y directions and this will give you the largest open area.
I also noticed that there is some type of duplication in the code that it may also be refactored by adding a couple of smaller functions to the class, but for showing the algorithm I don't think it is really needed in this case. The only double for loop this algorithm has is when reading in data from the file. The actual calculation works from a linear vector of coordinate pairs. There are 3 single for loops which traverse over the vectors. The first two are the same once in the x direction and once in the y direction. So the time is based on the size or length of the input N. This should be constant time. The last for loop will be still be N but looking into a vector of size N+1 which is still constant time where N is the number of towers or coordinate pairs. The trade off is that there is a little bit of memory overhead due to the local vectors to store the differences in the x & y values and for small and moderate data sets this shouldn't be a concern.
Disclaimer
This was mentioned in a comment to my answer:
Thank you for the effort, and sorry if this comes about negatively... but I wonder when people will ever teach this type of "encapsulation" into "classes" as part of the OO curriculum... This might be my very personal taste, but private member functions taking no arguments and returning void are a somewhat red flag to me. When reading code, having to track all members that might be modified is just as bad as having global variables like in the dark ages of programming. And in this particular case, they help hide the bug that the second test case uses both the towers from test case 1 and 2
Yes there was a bug in the code and I had fixed that as stated above. Now if one looks at the overall design of this class object or OO approach they will see that the implementation is hidden from the user or caller of this class object. There is a specific order of what his happening here.
Algorithm In Steps
- Declaring an object of this type with a user defined constructor.
- Constructor takes a string for a filename to read data in.
- The file is opened and if successful it starts to read data in otherwise throws an exception.
- It finds out how many test cases there are and for each test case it does the following:
- Retrieves the number of towers.
- Gets the coordinate positions of each tower in this test case.
- Calculates the Penalty for all towers of this test case.
- Stores the penalty value for this case.
- Repeats this process for all test cases.
- Closes the file stream.
- Construction of object completed.
- Now the object is complete and the only thing that is left over is for the user to call its public interface method to retrieve the penalty values.
Additional Features - These Could Be Added -
- Bounds Checking of Tower Coordinates against Grid MxN Size.
- Statistics of all cases - Repetitions, Average, Median, Mode, Standard Deviation, etc.
- Built in printing methods.
- Additional Container to store all the tower cell locations with their associated penalty value for each test case.
- More Error Checking.
- Some Refactoring & Efficiency Improvements.
Amendment lisyarus made a good point in the comments and based on that here is the non OO version.
#include <string>
#include <vector>
#include <algorithm>
#include <fstream>
struct TowerCoordinate {
unsigned x;
unsigned y;
TowerCoordinate() : x(0), y(0) {}
TowerCoordinate( unsigned xIn, unsigned yIn ) : x( xIn ), y( yIn ) {}
};
struct GridSize {
unsigned width;
unsigned height;
GridSize() : width( 0 ), height( 0 ) {}
GridSize( unsigned widthIn, unsigned heightIn ) : width( widthIn ), height( heightIn ) {}
};
bool compareCoordsX( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
return a.x > b.x;
}
bool compareCoordsY( const struct TowerCoordinate& a, const struct TowerCoordinate& b ) {
return a.y > b.y;
}
// Returns A Single Penalty
unsigned calculatePenalties( std::vector<TowerCoordinate>& towerLocations, GridSize& gridSize ) {
std::vector<unsigned> xValDiff, yValDiff;
unsigned diff = 0;
unsigned idx = 0;
// First Sort By Largest X - Then Find All Differences
std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsX );
for ( ; idx < towerLocations.size(); ++idx ) {
if ( idx == 0 ) {
diff = gridSize.width - towerLocations[idx].x;
xValDiff.push_back( diff );
} else {
diff = towerLocations[idx-1].x - towerLocations[idx].x - 1; // Don't Forget To Subtract 1
xValDiff.push_back( diff );
}
}
// Also Push Back (Last Value - 1)
xValDiff.push_back( towerLocations.back().x - 1 );
// Sort By Largest Y - Then Find All Differences
// First Sort By Largest X - Then Find All Differences
idx = 0;
diff = 0;
std::stable_sort( towerLocations.begin(), towerLocations.end(), compareCoordsY );
for ( ; idx < towerLocations.size(); ++idx ) {
if ( idx == 0 ) {
diff = gridSize.height - towerLocations[idx].y;
yValDiff.push_back( diff );
} else {
diff = towerLocations[idx-1].y - towerLocations[idx].y - 1; // Don't Forget To Subtract 1
yValDiff.push_back( diff );
}
}
// Also Push Back (Last Value - 1)
yValDiff.push_back( towerLocations.back().y - 1 );
unsigned largestX = xValDiff[0];
unsigned largestY = yValDiff[0];
idx = 0;
for ( ; idx < towerLocations.size(); ++idx ) {
if ( xValDiff[idx] > largestX ) {
largestX = xValDiff[idx];
}
if ( yValDiff[idx] > largestY ) {
largestY = yValDiff[idx];
}
}
return (largestX * largestY);
}
// Returns The Results Of All The Penalties For Each Case
std::vector<unsigned> getDefenderDataFromFile( const std::string& filename, unsigned& numTestCases, GridSize& gridSize, unsigned& numTowers, std::vector<TowerCoordinate>& towerLocations ) {
std::ifstream file;
file.open( filename );
if ( !file.is_open() ) {
// This ExceptionHandler will not work for you; you will need to supply your own error or exception handling.
std::ostringstream strStream;
strStream << __FUNCTION__ << " failed to read in file[" << filename << "]";
throw ExceptionHandler( strStream );
}
file >> numTestCases;
TowerCoordinate towerCoord;
std::vector<unsigned> penalties;
for ( unsigned t = 0; t < numTestCases; ++t ) {
file >> gridSize.width;
file >> gridSize.height;
file >> numTowers;
for ( unsigned c = 0; c < numTowers; ++c ) {
file >> towerCoord.x;
file >> towerCoord.y;
towerLocations.push_back( towerCoord );
}
unsigned currentPenalty = calculatePenalties( towerLocations, gridSize );
penalties.push_back( currentPenalty );
towerLocations.clear();
}
file.close();
return penalties;
}
int main() {
unsigned numTestCases = 0;
unsigned numTowers = 0;
GridSize gridSize;
std::vector<TowerCoordinate> towerLocations;
std::vector<unsigned> penalties;
penalties = getDefenderDataFromFile( "pieces.txt", numTestCases, gridSize, numTowers, towerLocations );
unsigned idx = 0;
for ( ; idx < penalties.size(); ++idx ) {
std::cout << penalties[idx] << " ";
}
std::cout << std::endl;
return 0;
}
The only thing to be aware of with this current implementation of this algorithm is that the vector of tower locations is being cleared after each test case so once you have the final results of all the penalties the container of tower coords on the current stack frame will only consist of the very last set of positions and will not contain any previous iterations of them. And once again there is no bounds checking of the tower coordinates against the grid size.
It is one kind of chess and rook problem variation.
Just think about maximum adjacent gap of co_ordinate on y axis, maxY_by_adjacent.
Just think about maximum adjacent gap of co_ordinate on X axis ,maxX_by_adjacent.
To find adjacent gap make them sorted first.
This will make longest undefended rectangle width=maxX_by_adjacent & height=maxY_by_adjacent.
Now, find out the number of cells on this rectangle maxX_by_adjacent * maxY_by_adjacent.
int h,w,n;
scanf("%d %d %d",&w,&h,&n);
int x[n+2];
int y[n+2];
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x[i],&y[i]);
}
x[0] = 0;
x[n+1] = w + 1;
y[0] = 0;
y[n+1] = h + 1;
sort(x,x+n+1);
sort(y,y+n+1);
int maxX_by_adjacent=0;
int maxY_by_adjacent=0;
for(int i=1;i<=n+1;i++)
{
maxX_by_adjacent=max(maxX_by_adjacent,x[i]-x[i-1]-1);
}
for(int i=1;i<=n+1;i++)
{
maxY_by_adjacent=max(maxY_by_adjacent,y[i]-y[i-1]-1);
}
int ans=maxX_by_adjacent*maxY_by_adjacent;
printf("%d\n",ans);
You can use greedy approach to solve this problem.Our aim is to find the largest undefended rectangle.Rectangle area = number of rows * number of cols.We have to maximize both these parameters.To find the maximum number of columns in the rectangle,sort the x coordintes of walls and take the difference between two consecutive x coordinate.Maximum of this difference will be the maximum number of columns in our final rectangle. Do samething to find number of rows in the final rectangle.Refer my code.https://github.com/sahazeer123/SPOJ/blob/master/DEFKING.cpp
加载中,请稍侯......
精彩评论