Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

helppppp please, in C please and with comments so I can understand better and know exactly what to do I'm new in this Objective Give

helppppp please, in C please and with comments so I can understand better and know exactly what to do I'm new in this

image text in transcribed

image text in transcribed

image text in transcribed

image text in transcribed

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 sns 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 Sr, cs 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 Output Sample Input 3 1 1 5 5 6 1 1 3 0 1 1 4 1 1 2 1 41 22 1 2 3 3 1 4 1 2 1 2 Explanation Case 1 There are 3 rooks. The grid looks like the following, 3 2 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 struct piece void add PieceToBoard (struct rankArrayList board, newPiece); void expandBoard (struct rankArrayList + board) ; void cleanBoard (struct rankArrayList * board) ; struct rankArrayList * createBoard () ; void addPieceToRank (struct rank * rank, struct piece * new Piece) ; void expandRank (struct rank * curRank) ; void cleanRank (struct rank* curRank); struct rank * createRank ()

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Database Security

Authors: Alfred Basta, Melissa Zgola

1st Edition

1435453905, 978-1435453906

More Books

Students also viewed these Databases questions