Problem Statement
A ball is moving diagonally on a rectangular board composed of unit squares in rows rows and columns columns. Each square is identified by its row and column number. The lowermost row is marked row 0 and the leftmost column is column 0.
The ball is initially located in the middle of a starting square given by two integers, startrow and startcol, and is moving diagonally up-right at an angle of 45 degrees. Whenever it reaches a wall, it bounces off it at a right angle (an angle of 90 degrees) and continues moving. If the ball runs into a corner, it bounces back in the opposite direction from which it came..
A number of holes have been drilled in the board and the ball will fall in upon reaching a square with a hole. Given the board size, starting location and locations of holes, return the number of times the ball will bounce off a wall before falling into a hole, or -1 if the ball will continue bouncing indefinitely.
Definition
- Class:
- BallBouncing
- Method:
- bounces
- Parameters:
- int, int, int, int, String[]
- Returns:
- int
- Method signature:
- int bounces(int rows, int columns, int startrow, int startcol, String[] holes)
- (be sure your method is public)
Notes
- Bouncing back from a corner counts as only one bounce.
Constraints
- rows and columns will be between 1 and 1000000, inclusive.
- startrow will be between 0 and rows-1, inclusive.
- startcol will be between 0 and columns-1, inclusive.
- holes will contain between 0 and 50 elements, inclusive.
- Each element of holes will be formatted as "row column" (quotes for clarity), where row and column will be integers with no leading zeros representing a square inside the board.
- There will be no holes at the starting position of the ball.
- No two holes will occupy the same position on the board.
Examples
8
11
2
1
{ "1 5", "5 3", "4 4" }
Returns: 3
This example corresponds to the image in the problem statement.
6
5
5
3
{ "1 3" }
Returns: 7
Bouncing back from a corner counts as only one bounce.
6
7
4
4
{ }
Returns: -1
With no holes, the ball is bound to bounce around for quite a while.
3
3
1
1
{ "2 2" }
Returns: 0
5
3
0
0
{ "3 1" }
Returns: 6
668
527
102
94
{ "3 362", "311 344", "34 367", "49 402", "158 280", "198 269", "256 211" }
Returns: 290
1000000
999999
0
0
{ }
Returns: -1
6
6
0
5
{ "4 1", "3 2", "4 3", "2 1", "3 0", "5 2" }
Returns: -1
83
77
82
76
{ "24 54", "6 3", "41 33", "67 60", "18 70", "69 16", "46 29", "45 20", "50 31", "15 27", "46 68", "50 21", "60 48", "39 70", "42 13", "14 44", "7 73", "80 38", "34 75", "64 21", "53 10", "3 54", "40 63" }
Returns: 11
ball in upper right corner
89
69
0
68
{ "86 18", "42 31", "25 22", "15 20", "24 33", "16 61", "50 33", "49 0", "57 6", "32 3", "22 4", "40 15", "1 20", "49 34", "83 19", "15 53", "15 16", "71 6", "65 48", "16 64", "16 4", "12 44", "87 23", "4 39", "34 6", "75 38", "19 21", "63 56", "85 13", "83 34", "65 27" }
Returns: 13
ball in lower right corner
82
53
81
0
{ "41 5", "65 47", "29 52", "78 51", "7 34", "68 2", "30 19", "45 46", "6 50", "3 6", "25 22", "57 25", "12 1", "1 20", "20 52", "40 0", "30 37", "59 19", "23 43", "40 41", "33 27", "61 24", "9 42", "61 51", "80 23", "67 21", "51 26", "70 36", "18 36", "59 25", "40 25", "65 15", "3 10", "15 2", "12 2", "0 11", "4 24" }
Returns: 1
ball in upper left corner
97
96
0
0
{ "47 34", "5 67", "9 3", "5 94", "6 64", "2 33", "26 78", "26 13", "29 55", "43 42", "27 82", "20 83", "55 51", "70 32", "42 31", "57 79", "51 34", "53 6", "25 65", "47 4", "27 5", "62 19", "2 27", "89 57", "36 76", "58 5", "18 24", "44 41", "82 7", "96 48", "84 35", "88 4", "31 56" }
Returns: 6
ball in lower left corner
98
84
84
18
{ "75 55", "47 83", "11 68", "90 46", "58 22", "8 63", "89 63", "41 49", "65 77", "55 20", "48 7", "46 63", "39 59", "83 17", "82 16", "81 15" }
Returns: 26
holes on the starting diagonal, but below the starting position
1000000
999999
1
1
{ "0 0" }
Returns: 3999995
huge return
987
1
13
0
{ "1 0" }
Returns: 1959
one column
1
4732
0
131
{ "0 4371" }
Returns: 4240
one row
1
10000
0
0
{ "0 9999" }
Returns: 9999
one row, hole in corner
999999
1
0
0
{ "999998 0" }
Returns: 999998
one column, hole in corner
23757
953443
11659
523894
{ "4833 925642", "8162 675942", "3986 873506", "10961 459266", "15231 93645", "1858 107716", "22310 197749", "6302 79472", "20972 199072", "17138 315831", "14776 8248", "14348 758269", "7527 756454", "3807 739625", "18826 28260", "12917 55912", "17841 492566", "20519 538818", "17840 721291", "14339 202385", "19737 155072", "4466 836685", "16574 200558", "18228 74979", "17405 417497", "13553 865176", "2519 444682", "20551 712978", "22462 847617", "21547 204208", "20819 19567", "12791 805032", "287 934536", "8890 254637", "18915 348274", "14961 628080", "6927 330530", "9755 251274", "20059 206480", "18729 689069", "23026 580667", "13955 248629", "8522 175666", "18575 32480", "19608 280356" }
Returns: 19784
random large case
86000
403824
25162
151823
{ "71672 186197", "62171 44210", "28898 286926", "77467 283389", "4547 311415", "79848 98905", "64668 203791", "37024 252417", "70900 101719", "27096 8657", "75243 126740", "64102 306955", "38357 391753", "76351 83055", "74056 335520", "16617 148768", "73567 163256", "32043 386484", "41332 397298", "4629 64652", "71955 352434", "9664 339405", "70380 210132", "63039 344438", "58006 133287" }
Returns: 51786
random large case
754601
709403
608835
433199
{ "278665 478110", "398063 278128", "578293 628986", "567442 595668", "513120 330267", "666453 26198", "377816 192532", "321902 681200", "523086 641380", "193730 633279", "274808 153014", "643215 424577", "428794 417731", "19528 188725", "468383 425623", "194272 496583", "582363 409010", "387220 462464", "649659 587723", "139567 391092", "364052 172198", "554069 119951", "711978 571401", "503509 567634", "653065 479859", "271067 414576", "409241 300040", "123542 549938", "145788 157184", "420851 97320", "507360 357816", "43868 337386", "621464 170973", "748369 426210", "496180 126372", "17992 556290" }
Returns: 78710
random large case
569206
915283
194440
854068
{ "257196 365895", "13282 74449", "331224 256378", "165712 553192", "417964 607881", "123757 390421", "308060 280185", "539620 440215", "256942 564485", "169712 367067", "285770 657875", "247817 476359", "202674 893503", "413141 555371", "506843 544368", "518730 272298", "524764 145100", "213189 56623", "289843 787071", "183016 822894", "293238 112469", "467531 668198", "133933 143456", "460171 862077", "6718 334163", "410092 832981", "554426 750571", "362765 200644", "547733 703352", "195608 763131" }
Returns: 26811
random large case
755482
527417
465359
372463
{ "232262 12486", "538192 309366", "672465 353950", "626692 358632" }
Returns: 61988
random large case
44516
632448
20839
610065
{ "43860 247088", "13731 432698", "5690 152600", "29472 567964", "38097 479178", "1579 530757", "31319 91300", "27924 187297", "19080 460138", "12540 403220", "11329 430627", "31812 78018", "3979 217348", "14177 310807", "9920 498498", "2910 110270", "2949 327928", "30956 589870", "35188 178634", "4887 59504", "7293 107657", "2776 60056", "1058 507781", "18213 295171", "1344 441779", "37682 533", "23260 311575", "4494 386021", "17505 48386", "42710 76774", "27811 384162", "43182 591625", "8352 416845", "19217 198357", "5358 606885", "37251 405131", "24161 151111", "22390 428536", "12637 336952" }
Returns: 20389
random large case
737289
55410
666601
51251
{ "433880 52641", "513518 29521", "246994 10967", "253218 52645", "659595 32666", "481214 38589", "431061 8876", "291338 7584", "301245 11266", "607744 53417", "343929 53912", "48109 13176", "494263 21150", "107736 19568", "390554 19775", "465335 37025", "394235 43983", "568556 37948", "314167 50519", "547025 15588", "70736 31001", "136580 27505", "575159 30403", "382897 5055", "719897 35106", "346307 37583", "725832 13703", "141043 32231", "696438 50262", "93742 34122", "566002 32425", "155278 53048", "132772 2841", "560582 39084", "307224 4524", "661730 36134", "37827 50426", "197512 40118", "585416 35978", "583333 10831", "99300 7724", "514953 30315", "360306 26497" }
Returns: 13443
random large case
930215
445390
37304
192082
{ "107933 300975", "758842 204821", "376739 390996", "59627 77959", "149498 138373", "347433 36735", "759492 325367", "323167 162026", "348008 56071", "310170 195969", "740561 392365", "661802 324731", "14346 117062", "330156 349955", "71789 59933", "242206 28200", "131705 165216", "65087 337804", "702982 192126", "287972 390004", "913223 270472" }
Returns: 24250
random large case
660313
31061
649279
27755
{ "53748 24200", "323551 393", "127947 6325", "227746 2713", "243853 18176", "260302 13674", "60529 3722", "115899 7267", "605089 25233", "443521 14248", "603105 5252" }
Returns: 17027
random large case
586884
791368
433566
746749
{ "233981 400497", "185163 498237", "285749 372810" }
Returns: 155787
random large case
431812
468764
83249
384193
{ "287547 461260", "162550 210670", "287420 237750", "209067 14490", "183579 99439", "157245 81971", "286654 316644", "382194 246178", "142515 57289", "329586 406021", "336310 195175", "10984 160811", "299819 68794", "190940 222471", "396203 403043", "222756 66509", "122608 448492", "230758 46955", "4028 65056", "271305 278249", "149742 294865", "138816 23031", "132797 289886", "227429 431123", "32182 205274", "292830 111393", "175826 95215", "51876 114459", "235339 138049", "206715 407030", "37671 290318", "345626 250877", "100488 276458", "407473 349060", "352834 311872", "14306 243443", "88098 176928", "244125 191183", "82672 164618", "126520 174703" }
Returns: 3533
random large case
239017
225168
76852
100743
{ "219643 82216", "95040 184769", "141398 182744", "49580 58496", "185308 154674", "55604 53498", "97600 194927", "175127 2993", "76779 93635", "165198 139214", "34774 125960", "130793 108774", "85723 57729", "73618 47053", "53404 152928", "52413 60284", "77493 103825", "204806 19945", "149105 50247", "71799 79746", "9606 177301", "226753 118389", "105677 202136", "222841 61136", "95419 2482", "162749 60084", "224725 103550", "165746 20557", "42982 146920", "67553 47408", "69944 195318", "69613 215722", "157257 140987", "21948 80320", "110679 2021", "15775 111260", "83616 152957", "83295 178977", "206830 53664", "181184 151111", "52358 97632", "95379 89257", "131410 135963", "102600 171645", "131089 178906", "31904 187454", "118772 25605", "195639 128234", "110469 9885", "66099 175995" }
Returns: 715
random large case
266394
312439
199123
187607
{ "199349 252352", "253885 287514", "10399 244424", "23349 40419", "102156 71186", "78262 87919", "42136 180868", "101705 34344", "54608 251819", "224017 228921", "116812 78957", "18559 17079", "195017 203785", "246286 115656", "19894 198869", "64544 54707", "177845 288107", "15299 118766", "224983 161727", "154200 224215", "44267 65418", "104668 83660", "225891 119511", "3309 77009", "187693 154780", "204266 245035", "147170 282333", "234176 39374", "158288 263089", "265317 234907", "85722 198825", "144246 89646", "58018 131473", "119682 233218", "95185 37926", "111287 31652", "23707 26930", "200639 264970", "172488 243260" }
Returns: 76
random large case
124634
111914
86366
80849
{ "25423 25028", "26053 63637", "115452 81916", "27663 45760", "122565 84617", "18007 52631", "55589 60697", "15905 48426", "21551 108532", "119840 45916", "87546 97905", "101366 1958", "77184 19677", "45241 44489", "17367 8155", "32254 15351", "111931 71679" }
Returns: 35637
random large case
321200
311398
315927
274686
{ "35876 234813", "18424 282995", "33534 235473", "76619 45428", "130289 1375", "279377 174366", "198572 73183", "161108 299764", "73129 246040", "203497 208287", "282432 125681", "251033 288296", "280591 282511", "194647 103934", "114538 110118", "261631 104492", "70936 234496", "294467 276795", "296542 133401", "123946 162834", "157207 296766", "97593 52249", "35144 302431", "131836 183142", "123947 21421", "269106 47874", "129746 158449", "53437 133755", "211494 247291", "82288 68334" }
Returns: 29759
random large case
763480
267679
691223
179688
{ "197466 65744", "21013 260668", "63195 195393", "440965 33342", "742928 107009", "488868 53293", "751949 95745", "355427 178845", "497894 199405", "186655 158040", "725178 155184", "411642 202168" }
Returns: 68375
random large case
321713
769135
67222
36960
{ "15186 8420", "295085 105937", "71075 184088", "70044 29072", "301846 193527", "54018 364773", "100686 685657" }
Returns: 166064
random large case
689243
101966
145230
94114
{ "375190 63193", "305476 99607", "31751 70722", "649704 55824", "293742 101056", "185280 41281", "413368 98513", "614198 9645", "42107 74612", "527654 55865", "569572 80587", "586330 41299", "660355 28715", "83781 47027", "498962 75353", "565230 67781", "210250 81844", "555353 5428", "3907 52017", "332324 60321", "510366 82553", "59141 30697", "110208 24190", "585024 71478", "399319 53756", "624826 71889", "98554 9781", "29899 36439", "456583 56169", "650436 21392", "373250 57808", "284326 27420", "141574 21610", "363916 72945" }
Returns: 5960
random large case
421696
447105
167010
274651
{ "357746 222036", "37335 416080", "179047 22833", "207689 93475", "32194 1707", "109527 21181" }
Returns: 88277
random large case
489552
674519
180192
155592
{ "231842 535329", "302748 309161", "327600 180071", "143814 142719", "289158 535209", "90824 662150", "193655 279665", "120728 341749", "261685 412808", "24052 132614", "7505 378345", "300394 1211", "26654 653266", "6210 656632", "345273 41461", "52437 406107", "115900 358441", "408112 355933", "421585 600192", "175122 98580", "230182 230067", "361296 650698", "273873 428336", "415361 339159", "20444 324542", "257908 119740", "139055 233756", "99383 146007", "362952 645480", "158553 99465", "84644 79884", "394563 360704", "41030 11265", "239762 1203", "267781 170331", "127423 490585", "250674 182363" }
Returns: 8201
random large case
960169
52
628473
12
{ "483514 2", "498696 12", "851128 47", "421012 23", "471798 8", "499373 22", "831416 10", "24699 8", "293462 27", "316152 50", "927729 3", "521583 17", "148907 24", "405794 47", "922010 49", "231910 38", "317741 43", "70915 36", "773998 28", "320967 20", "882875 0", "613841 41", "896958 0", "525489 22", "406634 25", "295040 30", "309882 40", "196874 42" }
Returns: 82339
many more rows than columns
480010
17
436240
8
{ "365362 15", "46660 5", "163313 4", "11069 5", "243510 6", "121160 13", "455922 11", "419768 8" }
Returns: 28067
many more rows than columns
424624
83
155036
0
{ "145629 2", "354610 37", "73185 29", "38814 40", "33475 33", "106093 45", "358340 79", "197513 2", "304722 7", "317539 52", "182751 49", "75374 24", "414980 32", "334938 18", "391248 23", "130454 32", "327916 23", "174303 20", "47817 75", "93033 59", "7909 59" }
Returns: 36686
many more rows than columns
93927
23
48431
20
{ "27531 16" }
Returns: 13036
many more rows than columns
50594
82
28800
73
{ "47164 61", "1708 12", "31277 44", "12275 79", "17187 19", "4338 57", "33496 27", "35308 39", "50483 57", "36849 71", "23841 0", "536 63", "40806 44", "45057 65", "45835 42", "30955 26", "38502 50", "47040 75", "28242 35", "5176 23", "22845 1", "14253 18", "20154 54", "8536 78", "37479 77", "13440 51", "4045 16", "9322 12", "39636 37", "27986 43", "32180 62", "17653 80", "2516 67", "46873 73", "33673 78", "36449 37", "41910 76", "34406 18", "7494 44", "10550 68", "37223 81", "3251 15", "22675 70", "27643 55", "1846 72", "39002 10", "16948 79", "10884 59", "3179 63", "379 58" }
Returns: 608
many more rows than columns
700021
94
442752
48
{ "456085 8", "595497 18", "696607 70", "92278 40", "558999 27", "572001 80", "213994 78", "27213 66", "144822 85", "532933 38", "672622 2", "667723 79", "220848 13", "575121 70", "343231 76", "388224 12", "210166 92", "302553 24", "484669 75", "501908 9", "333232 72", "328676 28", "531355 87", "103793 90", "374385 35", "641291 50", "455092 29", "645632 20", "151574 60", "328653 90", "331617 38", "108493 80", "118174 57", "688960 62", "58779 81", "691475 72", "273053 45", "50533 2", "24061 35" }
Returns: 6202
many more rows than columns
55244
11
18189
3
{ "9411 9", "2051 8", "30550 0", "36104 10", "13558 0", "16705 6", "22606 10", "6480 8", "54237 3" }
Returns: 1124
many more rows than columns
685698
3
656779
1
{ "438621 1", "17127 2", "278027 1", "240683 1", "609134 0", "589447 2", "356742 0", "10788 1", "497477 0", "279022 2", "63396 2", "109744 0", "382096 0", "221887 1", "39344 0", "11779 1", "113741 1", "95095 1", "391019 1", "177889 1", "52714 0", "258999 2", "669709 0", "70336 0", "537183 0", "651392 1", "678173 0", "629971 1", "666948 0", "432595 1", "194864 0", "357018 2", "478357 1", "522361 1", "89424 2", "87439 1", "535968 1", "443995 1", "17047 0" }
Returns: 3390
many more rows than columns
518232
12
85798
3
{ "52161 2", "17481 1", "279890 10", "38060 7", "61252 7", "307373 9", "488959 5", "338398 8", "94561 9", "363276 3", "204399 7", "146509 10", "307715 4", "140749 1", "149621 0", "270311 0", "281779 7", "274433 6", "175461 5", "204942 8", "145718 0", "452195 2", "319271 1", "182846 4", "179791 1", "213493 1", "408000 5", "25086 6", "314198 11", "390238 9", "448898 3", "513563 10", "10172 11", "500415 6", "113844 0", "200504 1", "169195 3", "441074 5", "444328 4", "407552 7", "393765 10", "140924 10", "333857 8", "146706 5", "208622 10", "436588 6", "274398 10", "295351 11" }
Returns: 8087
many more rows than columns
16473
16
4619
3
{ "7595 14", "12415 15", "5778 15", "13171 10", "15259 5", "10287 5", "338 14", "13115 11", "9921 12", "14521 2", "822 0", "6362 15", "5308 12", "7122 5", "2145 15", "7057 0", "3098 9", "13579 7", "6318 0", "8136 4", "16285 5", "6004 7", "2853 10", "11140 13", "7734 7", "4982 2", "10686 8", "11365 13", "6596 14", "13764 9", "679 9", "6380 8", "5168 13", "12965 10", "642 1", "4368 12", "12372 2", "12062 15", "6490 6", "5175 5", "12427 8", "14872 13", "12459 11" }
Returns: 1128
many more rows than columns
93
226721
71
17445
{ "87 23246", "25 91240", "20 122637", "36 104394", "18 58628", "38 66173", "7 179505", "74 100999", "45 172777", "13 174641", "66 143830", "92 75608", "53 77502", "56 28247", "34 48116", "32 213437", "7 46127", "3 11391", "51 216344", "50 214935", "85 126295", "35 143112", "15 182897", "9 220406", "61 88861", "6 183015", "41 172076", "19 60743", "36 220457", "51 178257", "3 125434", "92 130162", "85 27707", "59 149965", "9 120800", "69 113899", "91 221485", "21 216972", "63 21078", "35 197607", "54 84678", "25 75195", "76 51712", "81 177747", "49 183912", "74 102907", "54 75611", "87 125270" }
Returns: 899
many more columns than rows
37
751777
30
422116
{ "23 244937", "17 210607", "24 467390", "24 678257", "20 421739", "12 443687", "5 196774" }
Returns: 128839
many more columns than rows
56
754674
51
691620
{ "16 357839", "11 287688", "5 281710", "55 649555", "30 732555", "48 137635", "11 48275", "53 88689", "17 584340", "22 664398", "10 375309", "21 229139" }
Returns: 27686
many more columns than rows
15
170839
13
11255
{ "7 117926", "6 120351", "4 69845", "10 165076", "12 136577", "12 160966", "5 24003", "13 134649", "10 12634", "13 138163", "10 119348", "14 96440" }
Returns: 43968
many more columns than rows
2
701985
0
569109
{ "0 587702", "0 603968", "0 41335", "0 265691", "1 159507", "0 100326", "1 256888", "1 66518", "0 523007", "0 351494", "0 179847", "0 609731", "1 128487", "1 464284", "1 595331", "0 561257", "1 59464", "0 653147", "1 639404", "1 664772", "1 142464", "1 59459", "0 536138", "1 255723", "1 522572", "1 650107", "0 28825", "0 580434", "1 508162", "0 588431", "0 566111", "1 62849", "1 228745", "1 97793", "1 626918", "0 370475", "1 490558", "0 384908", "1 371204", "1 362721" }
Returns: 13111
many more columns than rows
44
94673
21
6086
{ "24 30960", "2 74078", "23 87322", "8 37448", "0 11026", "7 19036", "28 85995", "10 79950", "13 80120", "6 64706", "17 21989", "13 28133", "34 67211", "17 75877", "23 36028", "21 5829", "1 15839", "9 28202", "30 26924", "17 17353", "17 22093", "10 69779", "43 41244", "12 60961", "5 7916", "25 16683", "24 77959", "42 36696", "8 27153", "4 52009" }
Returns: 4669
many more columns than rows
87
668458
33
121689
{ "1 625259", "52 193740", "68 382964", "63 278526", "56 584322", "47 441001", "32 170453", "49 573812", "65 200871", "39 480913", "14 544093", "41 315891", "73 498050", "31 303629", "63 401070", "75 571497", "45 397737", "63 180681", "41 548920", "24 444508" }
Returns: 69135
many more columns than rows
55
856008
6
640200
{ "44 701554", "23 494154", "27 293831", "41 208064", "7 192438", "48 225184", "27 470072", "17 142362", "42 850880", "21 121009", "25 775197", "4 399629", "43 369487", "46 179676", "53 781362", "22 103759", "47 316880", "53 356142", "24 708891" }
Returns: 25251
many more columns than rows
83
978134
5
182741
{ "52 716932", "13 514112", "60 909663", "0 580470", "37 516918", "38 949363", "9 117922", "15 977250", "59 8536" }
Returns: 268881
many more columns than rows
28
662452
15
550814
{ "23 531194", "26 61707", "11 636153", "19 398475", "11 160741", "0 45395", "23 54945", "18 118189", "1 455153", "16 234469", "25 126468", "19 425408", "22 531727", "18 549651", "5 340324", "6 199247", "18 640837", "24 422585", "22 139417", "0 454007", "22 455941", "22 539667", "6 505406", "16 174402", "0 161613", "13 170188" }
Returns: -1
many more columns than rows
625339
330002
57750
255986
{ "261510 163938" }
Returns: 245780
large board with few holes
282861
446006
36877
314579
{ "184097 431892" }
Returns: 540982
large board with few holes
805737
134121
799493
58679
{ "472455 33759", "736264 27171", "24373 2025", "387804 119966", "487324 45150" }
Returns: 10024
large board with few holes
621321
723323
213926
643811
{ "459574 138542", "152463 276835", "490984 28520" }
Returns: 872568
large board with few holes
280877
481811
120015
211107
{ "145782 437233", "280298 78154", "261198 196331", "256773 82413" }
Returns: 171363
large board with few holes
225426
239452
207968
46910
{ "50826 13623" }
Returns: 224616
large board with few holes
568413
400205
178185
368690
{ "454496 296374", "416638 301568" }
Returns: 115693
large board with few holes
372166
472320
275423
452796
{ "283808 152972", "48153 12596" }
Returns: 344301
large board with few holes
89379
170442
7678
127058
{ "81829 116277", "77408 57071", "3178 113270", "31183 54437" }
Returns: 12744
large board with few holes
499999
999998
0
0
{ }
Returns: -1
large board with few holes
499999
999998
0
0
{ "220935 667509", "421821 421267", "115650 507706", "413847 395691", "173802 841050", "65566 632297", "330444 495836", "340790 910415", "54768 977164", "144771 569199", "340050 995808", "301988 375869", "470407 304339", "456839 128312", "227978 256944", "94303 318365", "317651 960886", "62160 561371", "5803 956276", "184451 630023", "171750 739152", "235018 688813", "214828 649735", "425822 640541", "240856 511502", "222152 968099", "14822 461243", "160103 350375", "404837 498517", "450764 787090", "382577 137570", "361232 133900", "358639 893511", "80323 739303", "499319 381412", "465078 245561", "302156 454385", "388107 605990", "15046 866931", "54567 685656", "327463 965080", "244634 548146", "268076 328567", "412170 184034", "128414 208880", "376348 319967", "154623 33141", "489571 486800", "332071 511450", "262529 131392" }
Returns: -1
fifty holes, but still -1
545517
545517
272758
272758
{ "323478 186868", "404850 265589", "37351 416574", "142997 232355", "491972 516654", "115869 367814", "335040 483345", "158607 360207", "51592 520203", "484859 221101", "255098 474779", "224270 178754", "506094 519289", "97243 292690", "201799 216723", "400656 223673", "529077 19188", "482116 67877", "21204 177157", "4792 400804", "400689 312734", "311937 448191", "520894 267394", "116781 436645", "452880 30076", "89604 258352", "23644 439701", "6240 280079", "52529 443535", "238471 261637", "166791 54018", "437399 249667", "364935 356449", "178945 57075", "76458 259031", "71283 290099", "452046 301892", "123951 276339", "241177 198228", "96491 7408", "324230 249007", "542820 305054", "208412 83270", "416481 479707", "38517 107320", "82561 253835", "25194 22503", "296092 318359", "57683 152162", "240521 268647" }
Returns: -1
fifty holes, but still -1
187719
187719
42908
113296
{ "127233 4733", "155307 117274", "93939 144785", "102388 99468", "1072 57178", "98105 135963", "59559 118492", "168370 86516", "9314 141791", "25944 108110", "98585 87254", "5580 59226", "179687 106989", "146885 12443", "102675 36874", "3990 180511", "70384 49606", "131100 11348", "27315 101946", "370 164848", "109247 14658", "148615 67599", "90676 79205", "5566 10764", "53455 116883", "19091 58636", "128630 61216", "79476 114501", "146280 104293", "127367 3121", "20347 130038", "130685 1695", "70822 152831", "86314 165265", "142582 34748", "1912 110764", "124816 32463", "135717 58163", "9479 43415", "163043 122891", "161876 65168", "74528 179597", "144631 73128", "21507 86219", "52746 160512", "38834 89406", "88727 149999", "67512 13856", "133194 8506", "23933 98920" }
Returns: -1
fifty holes, but still -1
351369
351369
32896
206392
{ "236841 209215", "143710 96807", "282188 31824", "219038 275252", "211424 195442", "182869 257138", "76827 88032", "34813 334517", "137186 199518", "141993 279233", "349101 292462", "230809 323009", "287730 29861", "18034 304751", "168188 265261", "138752 67912", "5941 108821", "183218 328857", "337281 105496", "290496 34318", "217215 126799", "183573 168882", "314180 75652", "322690 83286", "68048 100795", "158387 37887", "146670 343", "290523 177104", "325524 301813", "27629 243878", "314497 336620", "186399 200565", "33391 337760", "290530 313704", "322988 169164", "90493 34650", "229250 71271", "123205 295555", "63934 241377", "46759 218984", "107789 111123", "8524 246804", "137947 71911", "25782 125942", "180062 70913", "255540 187362", "90684 156988", "312439 230140", "223026 65895", "83928 93652" }
Returns: -1
fifty holes, but still -1
167590
167590
30836
132870
{ "57001 66402", "149582 95498", "57413 35971", "6450 99803", "46136 121142", "83651 3261", "88258 93904", "8273 21721", "139636 10361", "160440 84607", "98591 35634", "126501 31802", "161476 44609", "62377 28792", "93400 193", "46650 116481", "77474 84847", "60096 64871", "119037 135183", "69232 140823", "106416 74952", "72761 10503", "154415 165205", "35127 101743", "26118 51241", "80408 41357", "52436 147634", "111021 52510", "128152 14309", "75592 15644", "95722 74228", "157168 145222", "120596 101469", "25846 69280", "100336 149914", "60676 139164", "76006 23508", "69926 57398", "55221 40706", "30605 147738", "94011 123658", "98533 112945", "27799 52052", "160780 6557", "118012 167536", "153264 47731", "127244 15998", "141728 146280", "20887 90453", "8850 83010" }
Returns: -1
fifty holes, but still -1
309463
309463
83248
223640
{ "111958 110970", "297167 242088", "175365 230422", "14533 276399", "102768 60216", "268499 243990", "222091 124861", "241489 76206", "90937 169359", "142641 305331", "147271 111268", "192294 35344", "181865 44683", "219922 227327", "220334 245721", "270116 156073", "95900 718", "20432 256201", "293231 123175", "235016 214478", "210625 152346", "56340 10830", "39611 145204", "275016 1766", "158817 276955", "85607 162029", "215074 125363", "202029 103556", "96933 297631", "267126 253537", "145727 119261", "93590 117224", "147390 299557", "180764 265186", "39603 285877", "249676 24201", "186401 51322", "91536 181523", "152697 153596", "280584 224273", "49142 86195", "153914 168329", "15391 224927", "119167 259323", "306858 40037", "264997 39192", "207413 46263", "165362 17499", "130470 287264", "213533 40500" }
Returns: -1
fifty holes, but still -1
967553
967553
846079
580075
{ "849234 82430", "204497 279770", "464681 257743", "183374 310927", "210058 797117", "47158 11689", "824296 378415", "955845 59095", "730277 197869", "388377 506944", "575232 761477", "865458 479379", "364929 510313", "522911 160817", "597018 590757", "433247 912285", "681855 759146", "624784 23037", "172323 190039", "520131 494549", "598141 283282", "672255 351949", "290624 260138", "636992 537815", "440080 434885", "720857 847482", "474967 22508", "447709 91229", "289887 337261", "85705 937628", "763044 870058", "953088 911185", "635109 691811", "885908 862704", "349092 317541", "27064 944133", "376968 795232", "115253 8003", "245386 554793", "733090 132875", "658077 706174", "404336 14296", "102069 460353", "322183 178234", "314535 383222", "499902 714478", "366798 497686", "732224 696889", "652359 171145", "831261 438049" }
Returns: -1
fifty holes, but still -1
909306
909306
575951
56619
{ "463791 138770", "266788 569572", "804250 70891", "378234 586591", "591294 586044", "418595 383445", "217621 570353", "800195 431863", "191945 901073", "391810 899665", "833686 874740", "808720 132352", "872519 765033", "890927 528951", "107268 445447", "548121 273626", "587023 223863", "739548 776152", "894448 312052", "141339 825366", "228691 810507", "27526 362483", "721982 864127", "904867 65777", "206596 545749", "582241 477265", "249419 306362", "102188 66085", "90950 781457", "28701 278235", "388820 145162", "630823 59737", "875074 73901", "156248 550890", "433313 202966", "555688 716715", "640347 238255", "142331 84354", "21915 641296", "279024 403061", "881868 436845", "673540 604166", "44096 663540", "880292 429972", "138225 144321", "544886 480344", "104060 341655", "869760 156476", "487154 222837", "547975 415302" }
Returns: -1
fifty holes, but still -1
472854
472854
417422
60067
{ "282256 388934", "414698 112297", "250040 399275", "17729 381442", "28591 457265", "78930 419386", "286075 195088", "168345 189090", "431817 65573", "142830 139504", "268683 208417", "106581 325640", "133505 138723", "411154 325338", "420943 234573", "277836 276383", "245555 233782", "164993 138851", "23444 293104", "291476 211669", "463513 390560", "397193 343802", "376182 280900", "321982 463819", "455201 346795", "117432 195067", "58618 224305", "257197 243875", "448793 303292", "427878 252232", "185778 149351", "373010 125688", "252772 438092", "120522 52860", "293531 360289", "170181 281235", "225036 60410", "213616 184170", "308446 80824", "157922 96244", "271632 34583", "363965 106998", "457252 293498", "445637 144026", "233228 82365", "276501 221811", "380224 46669", "250585 445815", "268129 40527", "393930 251124" }
Returns: -1
fifty holes, but still -1
543324
543324
175274
61464
{ "85752 456948", "348748 443226", "375111 481070", "244545 100018", "515860 359778", "64174 395991", "113434 288053", "281577 539940", "255504 327989", "50834 122437", "270941 344388", "23384 77160", "196071 122352", "122920 326920", "508413 104215", "518900 353605", "402940 358408", "119412 64563", "276127 242794", "538833 168813", "56506 449110", "206499 449269", "335763 346478", "282382 431269", "5185 469435", "120906 190234", "26962 376941", "349293 42285", "302715 236388", "523624 65981", "17153 312411", "9883 495121", "199044 321806", "421486 520702", "175149 183303", "425223 264401", "272033 349997", "166722 48153", "46634 213995", "467053 276296", "284196 122934", "118581 75133", "139453 431195", "493648 308315", "438910 529852", "148114 450601", "515922 240180", "129415 166461", "142413 461315", "269356 173872" }
Returns: -1
fifty holes, but still -1
442522
442522
413740
359944
{ "145772 155066", "94087 355777", "27777 364205", "19539 307044", "29315 349035", "433628 326234", "397691 21431", "339110 96358", "439566 248851", "110822 400928", "377351 320068", "361232 142515", "271872 248337", "345842 392902", "302008 302601", "224602 98675", "206275 139054", "36307 239048", "289335 385236", "293551 145516", "405333 246927", "261659 413401", "18064 419684", "367294 407573", "306458 292869", "136820 369685", "186238 274591", "365169 420679", "144563 232340", "370243 358246", "30660 116549", "138660 217843", "423462 299142", "305732 113854", "33763 292969", "25581 75646", "129057 159809", "416529 252674", "275427 354699", "127615 133392", "431785 275984", "101468 221093", "88716 322985", "143496 190072", "420689 277448", "143775 97874", "408635 13752", "383932 12640", "368123 30582", "17794 294157" }
Returns: -1
fifty holes, but still -1
917864
917864
87480
916022
{ "85851 4316", "152351 673347", "421172 572746", "138417 341350", "144617 283388", "897343 692988", "336113 361900", "232479 255834", "807898 201363", "111300 327061", "819106 234121", "867784 760074", "774140 255332", "749093 862767", "817155 852179", "770045 219145", "274473 754734", "414126 142676", "412462 104432", "668478 748550", "369423 353765", "855714 151588", "579124 460605", "649266 746167", "750019 807285", "153847 862404", "816897 553548", "246439 340491", "749510 233509", "60864 59316", "268008 413828", "23727 867309", "632053 398704", "641985 64409", "341416 456954", "609920 274814", "51669 417204", "357239 183960", "171587 751686", "740586 225856", "290506 436091", "635476 214819", "228146 229559", "915395 232606", "290152 201596", "155071 639457", "249804 174472", "701511 166659", "504251 785386", "828000 541" }
Returns: 3
large square board, but not -1
687035
687035
237480
161608
{ "195430 453123", "402009 63377", "522298 220502", "429787 204554", "668766 166830", "427858 253528", "439895 226921", "156555 6739", "257101 330066", "502105 44278", "133024 449798", "40122 140517", "321458 529672", "50231 200758", "584441 314809", "565581 151336", "303305 529697", "113991 38119", "40606 377804", "254571 143250", "574047 4254", "632513 350704", "629648 467189", "643630 545638", "116783 296316", "537831 136635", "245241 435138", "310111 108792", "434537 484594", "122759 301936", "309721 611624", "52314 295566", "280605 2368", "67096 437069", "603692 175266", "128293 280191", "98549 238706", "529491 190167", "315473 595270", "411394 224413", "191310 336169", "326348 659745", "66094 611988", "593026 197520", "571498 426086", "294979 76619", "686036 635801", "591986 264090", "83837 549594", "15749 164265" }
Returns: 4
large square board, 4
1000000
999999
66246
84332
{ "854350 4982" }
Returns: 1662562
5
7
3
4
{ "0 6", "2 3" }
Returns: 5
1
5
0
1
{ "0 3" }
Returns: 2
1
1
0
0
{ }
Returns: -1
1
2
0
0
{ }
Returns: -1
1
2
0
0
{ "0 1" }
Returns: 1
1
2
0
1
{ "0 0" }
Returns: 2
2
1
0
0
{ }
Returns: -1
2
1
0
0
{ "1 0" }
Returns: 1
2
1
1
0
{ "0 0" }
Returns: 2
1000000
999999
0
0
{"999950 0", "999951 0", "999952 0", "999953 0", "999954 0", "999955 0", "999956 0", "999957 0", "999958 0", "999959 0", "999960 0", "999961 0", "999962 0", "999963 0", "999964 0", "999965 0", "999966 0", "999967 0", "999968 0", "999969 0", "999970 0", "999971 0", "999972 0", "999973 0", "999974 0", "999975 0", "999976 0", "999977 0", "999978 0", "999979 0", "999980 0", "999981 0", "999982 0", "999983 0", "999984 0", "999985 0", "999986 0", "999987 0", "999988 0", "999989 0", "999990 0", "999991 0", "999992 0", "999993 0", "999994 0", "999995 0", "999996 0", "999997 0", "999998 0", "999999 0" }
Returns: 1999898
1000000
999999
66246
84332
{"854350 4982" }
Returns: 1662562
1000000
999999
66246
84332
{ }
Returns: -1
999999
999998
123456
745321
{"12221 44432", "324324 342231", "33111 44564" }
Returns: 2691839
1000000
1000000
0
0
{"0 1", "0 2", "0 3", "0 4", "0 5", "0 6", "0 7", "0 8", "0 9", "0 10", "0 11", "0 12", "0 13", "0 14", "0 15", "0 16", "0 17", "0 18", "0 19", "0 20", "0 21", "0 22", "0 23", "0 24", "0 25", "0 26", "0 27", "0 28", "0 29", "0 30", "0 31", "0 32", "0 33", "0 34", "0 35", "0 36", "0 37", "0 38", "0 39", "0 40", "0 41", "0 42", "0 43", "0 44", "0 45", "0 46", "0 47", "0 48", "0 49", "0 50" }
Returns: -1
1000000
999900
1
2
{"1 1", "2 2", "3 3", "4 4", "5 5", "6 6", "7 7", "8 8", "9 9", "10 10", "11 11", "12 12", "13 13", "14 14", "15 15", "16 16", "17 17", "18 18", "19 19", "20 20", "21 21", "22 22", "23 23", "24 24", "25 25", "26 26", "27 27", "28 28", "29 29", "30 30", "31 31", "32 32", "33 33", "34 34", "35 35", "36 36", "37 37", "38 38", "39 39", "40 40", "41 41", "42 42", "43 43", "44 44", "45 45", "46 46", "47 47", "48 48", "49 49", "50 50" }
Returns: -1
1000000
100000
100
101
{"99 100" }
Returns: 22
5
7
3
4
{"0 6", "2 3" }
Returns: 5
5
5
4
4
{"3 3" }
Returns: 1
1000000
999999
49999
999998
{"999999 999998" }
Returns: 2099997
732307
826891
243723
1
{"204397 1" }
Returns: 2668975