This is the task statement
http://www.spoj.com/problems/KFRIENDS/
We need to notice one very important fact. The answer can't exceed 8 because the knight on a chess board can have maximum 8 neighbours. When for example one knight has 8 neighbours he will wear 8 different color straps . Now let's consider on of his neighbours which is already wearing one strap. He also can have 8 neighbours at best but one of them is already considered (the first one) so we understood that the answer cannot be greater than 8. For calculating our answer we will need to calculate the number of neighbours of every knight and then pick the maximum. Just because the coordinates are 100 at most we can keep a 2 dimensional array (matrix) and loop over it once and find the number of neighbours of every knight. Pick the maximum of the found values and print.
DOWNLOAD THE FULL SOURCE CODE
http://www.spoj.com/problems/KFRIENDS/
We need to notice one very important fact. The answer can't exceed 8 because the knight on a chess board can have maximum 8 neighbours. When for example one knight has 8 neighbours he will wear 8 different color straps . Now let's consider on of his neighbours which is already wearing one strap. He also can have 8 neighbours at best but one of them is already considered (the first one) so we understood that the answer cannot be greater than 8. For calculating our answer we will need to calculate the number of neighbours of every knight and then pick the maximum. Just because the coordinates are 100 at most we can keep a 2 dimensional array (matrix) and loop over it once and find the number of neighbours of every knight. Pick the maximum of the found values and print.
No comments:
Post a Comment