Output should contain n lines. The i-th line will start with an integer t, representing the number
of rooks that can attack the i-th rook. Following t should be t integers on the same line. Each
integer will represent the ID of the rook that can attack the current rook. Each rook ID should
occur only once in the line. All integers in the line should be separated by spaces. Order of the
IDs does not matter.Chessland Attacks
Objective
Give practice with dynamic memory.
Give practice with array lists.
Story
In a nearby land there is quite the border dispute between many royal families. Each one has a
champion chess piece (a rook) on a large 2D grid. The royal families would like to know how
much peril their rook currently faces. Rooks can only attack other pieces in their rank or file
(row/column). Additionally, a rook can only attack another rook if there is no other piece(s)
directly in between the two.
Unfortunately, the board is so large it is hard to eyeball whether 2 rooks can attack each other.
You offer to solve the rook threat question in exchange for some coins.
Problem
You will be given the rank and file of many rooks. Your objective is to determine how many and
which rooks threaten each piece.
Input
Input will begin with a line containing 1 integers, n (1 ≤ n ≤ 100,000), representing the number of
rooks to process. The first line will be followed by n more lines. The i-th following line contains
two integers, r and c (1 ≤ r, c ≤ 1,000,000,000), representing the rank and file of the i-th rook.
The i-th rook will have the ID of i.
No two rooks will be in the same spot. The number of unique ranks and files will be at most
10,000.
Output
Output should contain n lines. The i-th line will start with an integer t, representing the number
of rooks that can attack the i-th rook. Following t should be t integers on the same line. Each
integer will represent the ID of the rook that can attack the current rook. Each rook ID should
occur only once in the line. All integers in the line should be separated by spaces. Order of the
IDs does not matter.
Sample Input
Sample Output
3
1 1
5 5
6 1
1 3
0
1 1
4
1
2
4
2
1
3
1
1
1
1
1
2
2
3 1 4
2
2
Explanation
Case 1
There are 3 rooks. The grid looks like the following,
3
2
1
1 and 3 can mutually attack each other. 2 cannot attack anyone.
Case 2
There are 3 rooks. The grid looks like the following,
3
2
4
1
1 and 2 can mutually attack each other. 3 and 2 can mutually attacke each other. 4 and 2 can
mutually attack each other.
Hints
Array list of Array lists: I recommend using a dynamically sized array for each row where only
the ids and locations of the rooks are stored inside. Trying to create arrays based on the size of
the board is not feasible. Also recommend using an arraylist to hold all the rows, and use some
integer to know which row corresponds to each spot of the array list.
The struct can look like the following,
struct rankArrayList {
int size, cap;
struct rank * ranks;
}
Rank struct: You can make a struct that stores the information for each row. The struct can
look like the following
struct rank {
int location;
int num_pieces;
int capacity;
struct piece * array;
};
Piece struct: You can make a struct that stores the information for each piece. The struct can
look like the following
struct piece {
int rank, file, id;
};
Doubling: It’s good practice to double the size of the array list when increasing capacity. It
ensures that the number of doublings occurs logarithmically with respect to the number of
elements.
Avoid Needless Checks: Storing pieces by their rank or file allows your program to quickly
check the important pieces for any possible threats (remember rooks can only attack in the
same row or column).
Storing Pieces Twice: It is a good idea to not only store the pieces by their rank but to also
store the pieces by their file to void needlessly checking which files a piece can attack.
Function Recommendations: I recommend making separate array list functions for the array
list of ranks and the rank themselves. The following prototypes are recommended
void addPieceToBoard(struct rankArrayList * board, struct piece *
newPiece);
void expandBoard(struct rankArrayList * board);
void cleanBoard(struct rankArrayList * board);
struct rankArrayList * createBoard();
void addPieceToRank(struct rank * rank, struct piece * newPiece);
void expandRank(struct rank * curRank);
void cleanRank(struct rank * curRank);
struct rank * createRank();
Grading Criteria
●
●
●
●
●
●
Read/Write from/to standard input/output (e.g. scanf/printf and no FILE *)
○ 10 points
Good comments, whitespace, and variable names
○ 15 points
Only check the pieces in the same row/column to increase performance.
○ 10 points
Store each piece in the program until all input has been read
○ 5 points
Check the four directions for each piece.
○ 10 points
Programs will be tested on 10 cases
○ 5 points each
Programs with extra output will be docked 10 points.
No points will be awarded to programs that do not compile using “gcc -std=gnu11 -lm”.
Sometime a requested technique will be given, and solutions without the requested technique
will have their maximum points total reduced. For this problem use dynamic memory (calloc,
malloc, realloc, free). Without this programs will earn at most 50 points!
Any case that causes a program to return a non-zero return code will be treated as wrong.
Additionally, any case that takes longer than the maximum allowed time (the max of {5 times my
solutions time, 10 seconds}) will also be treated as wrong.
No partial credit will be awarded for an incorrect case.
Purchase answer to see full
attachment
Why Choose Us
- 100% non-plagiarized Papers
- 24/7 /365 Service Available
- Affordable Prices
- Any Paper, Urgency, and Subject
- Will complete your papers in 6 hours
- On-time Delivery
- Money-back and Privacy guarantees
- Unlimited Amendments upon request
- Satisfaction guarantee
How it Works
- Click on the “Place Order” tab at the top menu or “Order Now” icon at the bottom and a new page will appear with an order form to be filled.
- Fill in your paper’s requirements in the "PAPER DETAILS" section.
- Fill in your paper’s academic level, deadline, and the required number of pages from the drop-down menus.
- Click “CREATE ACCOUNT & SIGN IN” to enter your registration details and get an account with us for record-keeping and then, click on “PROCEED TO CHECKOUT” at the bottom of the page.
- From there, the payment sections will show, follow the guided payment process and your order will be available for our writing team to work on it.