Untitled
user_9175993
plain_text
a year ago
9.1 kB
16
Indexable
Tàu vũ trụ chỉ có thể di chuyển theo hướng song song với trục X hoặc trục Y và mất 1 giây để di chuyển khoảng cách 1 đơn vị.
Do đó, thời gian mà tàu vũ trụ cần để di chuyển từ tọa độ (x1, y1) tới (x2, y2) được tính như sau:
Có tất cả N hố đen trong không gian. Ki là thời gian để di chuyển qua mỗi hố đen, mỗi hố đen có Ki khác nhau.
Và hố đen cho phép di chuyển theo 2 chiều.
Để thuận tiện, 2 lối vào của hố đen được gọi là Cổng A và Cổng B.
※ Không bắt buộc phải sử dụng tất cả hố đen để di chuyển tới điểm đích. Cũng có thể không cần dùng đến bất kì hố đen nào trong quá trình di chuyển.
Cũng không bắt buộc phải di chuyển qua hố đen mặc dù tàu vũ trụ gặp một cổng của hố đen đó.
▶ Cho thông tin về điểm bắt đầu và điểm đích (tọa độ) của tàu vũ trụ và thông tin về mỗi hố đen,
hãy tìm thời gian ngắn nhất để di chuyển từ điểm bắt đầu tới điểm đích.
[Giới hạn]
1. Số lượng hố đen N lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 5 (0 ≤ N ≤ 5).
2. Thời gian để di chuyển qua một hố đen Ki lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 3,000. (0 ≤ Ki ≤ 3,000)
3. X, Y, tọa độ trong vũ trụ lớn hơn hoặc bằng 0 và nhỏ hơn hoặc bằng 1,000. (0 ≤ X, Y ≤ 1,000)
4. Không có trường hợp nào mà tọa độ của điểm bắt đầu, điểm đích của tàu vũ trụ và tọa độ của những hố đen giống nhau.
[Input]
Dòng đầu tiên của là số lượng phép thử T. Từ dòng tiếp theo là thông tin về mỗi phép thử.
Dòng đầu tiên của mỗi phép thử là số lượng hố đen N.
Dòng thứ 2 là điểm bắt đầu [x1, y1] và điểm đích [x2, y2] của tàu vũ trụ.
Từ dòng thứ 3 tới dòng thứ ‘N+1’ là thông tin về mỗi hố đen.
Tọa độ [x, y] của Cổng A và [x, y] của Cổng B của mỗi hố đen, và thời gian để di chuyển qua hố đen.
[Output]
In “#T” cho phép thử thứ T, tiếp theo là một khoảng cách và in câu trả lời (T là số thứ tự của phép thử bắt đầu từ 1).
package Lesson_16;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Test_1 {
static int T, numberWhole;
static int pointX[], pointY[], value[][], min;
static boolean visited[][];
public static int calculatePoint(int x1, int x2, int y1, int y2){
return ( Math.abs(x2-x1) + Math.abs(y2-y1) );
}
public static void backTrack(int r, int c, int sumTime){
if(sumTime > min) return;
if(min > sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1])){
min = sumTime + calculatePoint(r, pointX[numberWhole+1], c, pointY[numberWhole+1]);
return;
}
for(int i = 1; i <= numberWhole; i++){
visited[value[i][0]][value[i][1]] = true;
visited[value[i][2]][value[i][3]] = true;
if(!visited[value[i][0]][value[i][1]]){
backTrack(value[i][2], value[i][3],
sumTime + value[i][4] + calculatePoint(r, value[i][0], c, value[i][1]));
}
if(!visited[value[i][2]][value[i][3]]){
backTrack(value[i][0], value[i][1],
sumTime + value[i][4] + calculatePoint(r, value[i][2], c, value[i][3]));
}
visited[value[i][0]][value[i][1]] = false;
visited[value[i][2]][value[i][3]] = false;
}
}
public static void main(String[] args) throws FileNotFoundException{
System.setIn(new FileInputStream("Test_1"));
Scanner scanner = new Scanner(System.in);
T = scanner.nextInt();
for(int tc = 1; tc <= T; tc++){
numberWhole = scanner.nextInt();
pointX = new int[numberWhole+2];
pointY = new int[numberWhole+2];
pointX[0] = scanner.nextInt();
pointY[0] = scanner.nextInt();
pointX[numberWhole+1] = scanner.nextInt();
pointY[numberWhole+1] = scanner.nextInt();
value = new int[numberWhole+1][5];
for(int i = 1; i <= numberWhole; i++){
value[i][0] = scanner.nextInt();
value[i][1] = scanner.nextInt();
value[i][2] = scanner.nextInt();
value[i][3] = scanner.nextInt();
value[i][4] = scanner.nextInt();
}
visited = new boolean[1001][1001];
min = calculatePoint(pointX[0], pointX[numberWhole+1],
pointY[0], pointY[numberWhole+1]);
visited[pointX[0]][pointY[0]] = true;
backTrack( pointX[0], pointY[0], 0);
System.out.println("#" + tc + " " + min);
}
}
}
50
0
0 0 60 60
1
0 0 2 0
1 0 1 2 0
1
0 0 60 60
40 40 20 20 10
2
100 50 10 5
80 40 10 6 10
80 10 70 40 5
3
500 500 1000 1000
501 501 999 999 1000
1 1 499 499 100
1000 999 0 0 200
1
252 854 366 380
242 449 680 162 1259
2
59 382 300 172
138 782 647 631 2652
5 692 376 250 1778
2
367 327 15 769
458 876 184 906 2753
201 839 237 914 1319
2
349 891 539 609
745 98 995 52 211
819 578 556 643 958
3
234 844 255 803
487 718 343 942 1782
208 212 815 788 1383
55 665 111 67 2010
3
967 956 183 221
524 23 166 439 1103
165 695 160 159 1609
962 48 784 637 83
3
132 166 344 269
12 988 362 491 1616
334 451 460 52 937
274 814 695 725 1754
5
864 480 355 621
511 700 265 665 2108
56 778 760 899 778
748 184 469 260 340
87 99 187 794 214
485 721 6 833 1390
5
716 105 730 903
618 726 366 901 354
511 458 381 290 2760
709 339 608 935 2389
258 813 20 306 1786
751 925 300 36 809
4
427 186 957 6
418 546 129 68 991
717 531 219 739 511
335 696 872 404 2886
114 919 772 883 2139
1
276 721 686 539
345 126 755 149 2120
0
103 186 984 440
1
470 238 174 241
973 934 25 839 281
4
603 856 437 739
8 520 44 221 2391
647 653 202 16 2141
132 859 975 8 629
80 422 596 348 1226
3
122 269 280 23
715 854 968 103 550
130 625 219 762 1302
569 216 213 613 2292
4
119 870 322 958
265 632 990 182 1817
289 300 288 572 340
153 635 693 203 669
168 647 40 443 2517
1
854 395 198 415
706 331 272 19 2021
4
860 206 795 355
344 60 468 822 1047
833 545 968 44 2117
521 895 417 719 1968
72 730 772 547 2389
0
450 94 637 265
5
535 692 969 762
86 921 753 581 784
679 919 201 948 621
706 549 453 192 2854
604 358 664 855 2508
924 637 134 178 282
2
962 177 909 317
403 663 513 658 1342
32 674 610 596 2068
2
325 637 379 737
144 214 110 472 908
957 530 468 734 2260
5
328 263 278 446
129 146 237 907 2338
601 908 402 215 1638
902 165 435 912 1924
948 756 143 49 2021
122 239 765 870 2192
1
838 241 944 892
574 147 146 103 1997
0
804 211 578 557
1
125 738 836 951
332 421 833 970 333
4
62 168 552 21
913 595 642 568 528
340 773 50 550 1560
452 181 668 889 2761
802 209 588 773 915
3
646 858 276 204
917 104 333 317 1495
588 504 970 838 1007
510 507 495 282 2389
4
827 738 392 899
99 140 741 810 906
497 780 483 644 2602
252 312 299 793 235
181 498 354 95 1284
3
44 572 389 805
441 607 389 25 1364
416 846 995 115 2399
620 941 787 59 675
1
132 276 547 199
94 89 658 500 1906
3
145 135 450 976
823 984 383 11 1194
397 441 300 665 2185
334 166 944 440 2329
3
614 843 830 168
366 62 604 187 661
798 949 913 972 2822
940 412 939 615 411
3
462 754 117 71
598 359 173 121 581
860 839 402 676 55
216 737 899 880 595
2
548 853 541 860
84 89 282 752 1566
678 189 195 135 857
1
511 771 591 91
159 897 869 520 1669
1
983 868 785 307
5 641 275 950 814
3
86 313 245 464
578 193 315 525 1224
30 599 865 387 940
814 821 857 177 901
5
73 992 196 827
26 623 997 712 169
921 211 657 143 1137
576 633 291 679 2854
152 84 914 353 1973
255 425 831 443 1593
0
927 872 684 974
5
952 571 77 244
497 885 942 465 1752
609 388 790 316 208
1000 453 534 781 2925
565 662 684 9 2457
952 195 444 858 1627
5
465 529 681 23
884 321 605 227 1322
747 464 494 606 1833
840 735 144 613 477
434 981 8 882 2870
163 657 147 501 1027
5
549 313 923 775
97 893 868 423 2237
378 319 1 735 168
171 926 292 587 1878
705 500 749 739 1563
968 511 96 690 823
5
208 403 82 797
334 626 243 511 884
745 728 682 505 1699
779 303 717 187 2830
93 203 109 108 57
904 378 888 51 2624
5
21 961 161 658
339 38 140 315 1733
428 767 216 222 2386
563 725 204 496 1269
55 121 850 896 1197
145 323 504 105 662
#1 120
#2 2
#3 90
#4 41
#5 305
#6 588
#7 451
#8 794
#9 472
#10 62
#11 1519
#12 315
#13 650
#14 812
#15 710
#16 592
#17 1135
#18 299
#19 283
#20 404
#21 291
#22 676
#23 214
#24 358
#25 504
#26 193
#27 154
#28 233
#29 757
#30 572
#31 879
#32 637
#33 1024
#34 596
#35 578
#36 492
#37 1146
#38 891
#39 1028
#40 14
#41 760
#42 759
#43 310
#44 288
#45 345
#46 1202
#47 722
#48 836
#49 520
#50 443Editor is loading...
Leave a Comment