Statistics

Problem Statement for "GetThemAll"

Problem Statement

You have an infinite chessboard with several black pieces placed on it. You have a white knight on the same chessboard, which starts from the (0, 0) point, and you want to know how fast it can capture all the black pieces.

You will be given a String[] pieces, containing information about black pieces. Each element of pieces will be formatted as "X Y", where X and Y are integer numbers between -1000000 and 1000000, inclusive. Your method should return the minimum number of moves needed to capture all the black pieces, assuming none of them move.

Definition

Class:
GetThemAll
Method:
quickKnight
Parameters:
String[]
Returns:
int
Method signature:
int quickKnight(String[] pieces)
(be sure your method is public)

Notes

  • A knight's jump moves him 2 cells along one of the axes, and 1 cell along the other one. In other words, if a knight is at (0,0), it may move to (-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2) or (1, 2).
  • The knight starts at (0, 0).

Constraints

  • pieces will contain between 0 and 9 elements, inclusive.
  • Each element of pieces will be formatted as "X Y", where X and Y are integer numbers without extra leading zeroes.
  • X and Y will be between -1000000 and 1000000, inclusive, in each element of pieces.
  • All elements of pieces will be different.
  • There are no pieces at (0, 0).

Examples

  1. {}

    Returns: 0

    An empty chessboard.

  2. {"1 2"}

    Returns: 1

    Just one move.

  3. {"2 -1", "2 1", "-2 1", "-2 -1"}

    Returns: 7

    The knight should return to the starting position several times.

  4. {"0 1"}

    Returns: 3

    The knight needs 3 jumps to move to any adjacent cell.

  5. {"0 7", "7 7", "7 0"}

    Returns: 15

  6. {"-3 -3", "-3 4", "4 4", "4 -3"}

    Returns: 17

  7. {"1000000 0", "1000000 1000000"}

    Returns: 1000000

  8. {"-1000000 -1000000", "1000000 1000000", "1000000 -1000000", "-1000000 1000000"}

    Returns: 3666668

    One really big square, containing the maximal possible distance between two pieces.

  9. {"-1000000 -1000000", "1000000 -1000000", "-1000000 1000000", "-300000 300000", "1000000 1000000", "500000 -400000", "-500001 -100000", "500700 408000", "500200 -401000"}

    Returns: 3817872

  10. {"127171 -613392","617481 170019","-40254 -299417", "791925 645680","493210 -651784"}

    Returns: 1141931

  11. {"127171 -613392"}

    Returns: 306697

  12. {"170019 -40254","-299417 791925","645680 493210","-651784 717887","421003 27070","-392010 -970031","-817195 -271096","-705375 -668203"}

    Returns: 1990421

  13. {"-108615 -761834","-990662 -982178","-244240 63326","142369 203528","214332 -667532","326090 -98422","-295755 -885922","215369 566637","605213 39766"}

    Returns: 1839346

  14. {"751946 453353","911802 851436","78707 -715324"}

    Returns: 1170678

  15. {"-529344 724479","-580798 559313","687308 993592","999390 222999","-215125 -467574"}

    Returns: 1823439

  16. {"680288 -952514","-248268 -814753","354412 -887570"}

    Returns: 871656

  17. {"837581 -448226"}

    Returns: 428603

  18. {"175817 382367","675222 452986","-30122 -589282"}

    Returns: 1023426

  19. {"-63082 -84079","898313 488876","-783441 198096","-229530 470016","217933 144810","-277322 -696891","-549791 -149693"}

    Returns: 1698869

  20. {"34211 979980","503098 -308878","-662038 314615","-16205 -872921","399518 9613","-705008 899167","-716850 810236","385785 -393903"}

    Returns: 1993133

  21. {"-859249 933226","366375 -693533","754509 643361","164098 -617298"}

    Returns: 1885117

  22. {"634389 -49471","-688895 7843"}

    Returns: 978838

  23. {"-188818 -440840","137486 364483","511704 443831","-49409 -753960","-264382 669363","-929808 34028","325968 -147557"}

    Returns: 1856216

  24. {"898679 842769"}

    Returns: 580484

  25. {"-308023 -56551","-250038 693961","-366253 -87802","-456221 965942","-404401 478378"}

    Returns: 749633

  26. {"-608021 522630","678885 -204688","1801 780328","-945067 989258","145177 -898984","62655 -611866"}

    Returns: 1985667

  27. {"253517 315226","-604297 684317","-753350 -780145","486252 -371868","882138 -427839","-327372 -719474","466170 669241","415998 200476"}

    Returns: 2428637

  28. {"-494553 -711051","-996766 -877987","612476 705253","-578845 -768792","106418 -971496","-772454 -90976","504441 372295"}

    Returns: 2136078

  29. {"-852230 -126560","-596118 392438","-419294 -126621","-535142 155736","65157 257363"}

    Returns: 935320

  30. {"8271 926085","391522 849605"}

    Returns: 616430

  31. {"-328105 -643300","990357 -85116"}

    Returns: 983035

  32. {"-804987 250343","-811213 -124546","863033 -903135","789240 -419965","-545397 538133","-178564 -596057","256142 208289","-96774 -67293","195654 269448"}

    Returns: 2096808

  33. {"657583 249550","441817 131504","-249733 -631459","475814 110263","810175 -514268","-622120 209449","397015 169225","-297403 -11078"}

    Returns: 1755255

  34. {"481491 224098"}

    Returns: 240747

  35. {"382245 609058","-701773 152074","735466 823115","229408 455367","-913572 335551","953063 -369976"}

    Returns: 1941953

  36. {"-388348 -652150","-782892 738091","702445 488632","-690237 -346172","-841304 -846798","281961 640004"}

    Returns: 2108427

  37. {"-103488 -182043","-402509 -68880","2411 -694693","-353923 475997","-372234 653371"}

    Returns: 1056207

  38. {"746697 450057","-399884 887998","-745537 -868527","569933 49165","219276 912229","-855465 751275","307718 -355754","-790399 10102","-545824 -419416"}

    Returns: 2331062

  39. {"102329 325602","-770928 -14924","-241737 -6378","586719 18525","-235267 376324","64303 212562","-209632 -988220","415754 -798761","246132 726493"}

    Returns: 2181168

  40. {"494675 -6195","-239784 570727","105625 -285806","911436 261696","-646840 -251503"}

    Returns: 1523820

  41. {"486557 903440","223975 -944335"}

    Returns: 1387222

  42. {"-888181 278421","-736748 694144","728630 193762"}

    Returns: 1304868

  43. {"707938 -970642","-747063 415815","234291 -564867","-868099 -662160","248207 -318034","-361187 -264870","322001 604786"}

    Returns: 2405110

  44. {"53072 222205","596362 801203","-710380 260354","-195166 -492600","-726921 710380","-867672 -144383","146703 -395429","96103 -548876"}

    Returns: 1984519

  45. {"-778741 616077","-730583 -431501","576220 790460"}

    Returns: 1588634

  46. {"487594 230445","-277749 713309","-543016 727165","-541124 -500901","84811 969665","-892392 -837154","49348 -146397","-810664 -482406"}

    Returns: 1990684

  47. {"-534471 -706901","-749810 863278","-839778 -905820","-882565 -327189","829402 -202796","-134434 892331","674368 68453","684195 387066","-204627 -481674"}

    Returns: 2528878

  48. {"51180 909605"}

    Returns: 454803

  49. {"-517808 171117","-489731 368023","890561 -129002","780450 -985657"}

    Returns: 1475833

  50. {"203101 572314","153356 -715141","-555346 -233986","-991455 -164159","-835506 319865","710197 -870297","622120 324137","382977 605396","60274 371258"}

    Returns: 2276454

  51. {"379010 455794","555468 -937865"}

    Returns: 975099

  52. {"289041 413129","-829097 103977","895810 -882443","-450057 -709647","963561 239967","-415510 844966","-264931 389081","-562731 -688162"}

    Returns: 2627231

  53. {"42879 804560","-787164 805292","-116550 -839778"}

    Returns: 1639840

  54. {"-656423 948790","551744 740776","-578723 -86764","-992493 501267","-771905 -190588","-377728 985230","-922850 -495834","-621449 -504624"}

    Returns: 1976904

  55. {"240639 770745","878171 -608692"}

    Returns: 1075093

  56. {"291116 313517","818293 -89084","842586 328349","-698477 272683","139073 -155919","886044 81149","157140 72909","-489426 -206092"}

    Returns: 1581136

  57. {"-926756 590503","-606983 -859432","-221168 181494","-858150 -604664"}

    Returns: 1271985

  58. {"288675 -91342","208594 394696"}

    Returns: 387358

  59. {"368938 -206946","671438 184423","-600818 898923","752007 -216590"}

    Returns: 1246257

  60. {"-629384 791437","148900 -115879","254677 417036","-900754 -428877","-479599 -184729","790643 420393","456893 792108","-212867 -205176","807734 -382794"}

    Returns: 2505650

  61. {"141148 -292886","467391 490707","472762 478866","-721366 -599658"}

    Returns: 1142422

  62. {"360882 822261","-264321 35310","-781244 814875"}

    Returns: 1135389

  63. {"35920 309671","-122959 375286"}

    Returns: 234277

  64. {"-840877 -848446"}

    Returns: 563109

  65. {"-289834 -385541"}

    Returns: 225125

  66. {"-714652 -210303","-864315 351482","449874 -602588","388043 231422","309794 87985","-803400 90732","-900754 949157"}

    Returns: 1787667

  67. {"939940 455733","61922 359844","385602 -255776","-222755 -900083","619557 -660879"}

    Returns: 1675056

  68. {"-378887 568957"}

    Returns: 315948

  69. {"-356182 -30671","-981689 -120274"}

    Returns: 490845

  70. {"211890 517075","-197852 -300394","685293 884640","246620 994568","-893064 125706"}

    Returns: 1550415

  71. { "100 40", "20 40", "23 10", "-5699 342", "-123 1233", "-89 0", "-1 -1", "-89 0" }

    Returns: 3543

  72. { "-1000000 -1000000", "1000000 1000000", "1000000 -1000000", "-1000000 1000000", "1 1", "-1 -1", "1 -1", "1 1", "500000 500000" }

    Returns: 3666674

  73. { "100 40", "20 40", "23 10", "-5699 342", "-123 1233", "-89 0", "-1 -1" }

    Returns: 3543

  74. { "5 2" }

    Returns: 3

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: