armybrave
quoc14
c_cpp
5 months ago
10 kB
2
Indexable
caidat
#include <iostream>
using namespace std;
int m, n, x_start, y_start;
int a[50][50];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, -1, 1};
int max_ans;
int visit[50][50];
int maxx(int a, int b) {
if (a > b) return a;
return b;
}
bool inside(int x, int y) {
if (x >= 1 && x <= m && y >= 1 && y <= n) {
if (a[x][y] != 0) {
return true;
}
}
return false;
}
void backtrack(int x_cur, int y_cur, int cur_army, int country) {
max_ans = maxx(country, max_ans);
for (int i = 0; i < 4; i++) {
int x_next = x_cur + dx[i];
int y_next = y_cur + dy[i];
if (inside(x_next, y_next) && a[x_next][y_next] <= cur_army && visit[x_next][y_next] == 0) {
visit[x_next][y_next] = 1;
if (a[x_next][y_next] <= cur_army / 2) {
backtrack(x_next, y_next, cur_army + a[x_next][y_next], country + 1);
}
else {
backtrack(x_next, y_next, cur_army - a[x_next][y_next], country + 1);
}
visit[x_next][y_next] = 0;
}
}
}
void solve(int testcase) {
cin >> m >> n >> x_start >> y_start;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
visit[i][j] = 0;
}
}
max_ans = 0;
visit[x_start][y_start] = 1;
backtrack(x_start, y_start, a[x_start][y_start], 0);
cout << "#" << testcase << " " << max_ans << endl;
}
int main() {
//freopen("Text.txt", "r", stdin);
int t; cin >> t;
for (int i = 1; i <= t; i++) {
solve(i);
}
return 0;
}
50
4 4 1 1
20 8 7 33
10 0 0 2
12 9 12 30
39 1 23 9
5 5 2 2
3 0 15 0 17
0 15 8 12 8
7 6 8 11 13
2 12 13 4 17
12 0 1 15 2
5 5 3 1
19 2 20 9 1
11 10 20 9 0
14 13 9 19 13
13 6 5 11 1
4 16 15 9 0
5 5 3 3
3 3 12 17 19
7 4 19 2 13
18 14 1 8 0
3 2 19 20 12
11 20 18 8 4
5 5 4 5
10 18 4 0 2
13 14 14 13 17
4 12 8 8 0
6 19 4 10 12
16 14 20 10 19
5 5 2 4
8 14 8 15 13
0 20 0 9 1
17 1 5 19 5
7 14 14 14 13
7 13 11 1 9
7 7 1 5
871 933 757 365 488 427 695
370 379 880 222 699 938 36
212 0 0 22 544 960 628
161 660 701 0 819 784 826
904 95 231 473 0 604 968
868 953 539 773 182 707 934
646 0 436 159 800 650 298
7 7 6 1
443 63 87 742 501 530 70
621 10 150 851 969 963 148
908 80 56 919 0 75 338
0 0 0 0 0 0 0
924 504 152 401 315 421 930
164 11 978 331 43 27 136
360 362 842 537 414 893 552
7 7 3 2
773 507 0 433 75 449 900
872 761 0 327 989 879 347
591 680 0 0 69 136 928
129 340 932 749 166 287 551
623 803 396 258 700 222 171
925 531 319 853 266 854 844
916 951 656 844 130 702 974
7 7 4 4
960 584 651 552 246 801 871
212 497 298 0 309 160 288
397 644 0 176 2001 259 684
768 460 810 724 190 642 678
939 619 0 334 0 823 537
996 135 185 681 209 732 340
437 330 638 978 364 59 940
5 7 4 2
978 441 801 1925 1301 1596 1366
774 1681 1664 459 1116 1981 0
63 1615 712 763 1143 1139 352
432 644 1352 995 1599 1499 1246
604 162 558 1192 23 1016 253
6 6 6 4
125 774 725 260 1637 764
725 1976 733 1145 347 757
1667 566 188 926 504 799
781 1483 856 918 863 1541
1389 1845 987 0 46 947
259 597 362 1292 139 174
6 5 6 3
38 368 205 880 685
0 1335 245 0 314
693 24 1847 603 376
1140 1129 0 522 1930
839 0 549 1357 1331
309 947 675 34 0
5 5 1 2
370 314 1933 204 450
777 90 1890 0 75
1286 1448 991 257 160
866 445 1822 868 470
0 1688 764 1703 368
7 7 3 6
262 159 1277 0 0 3 1152
1524 209 0 0 0 1303 1476
1580 389 302 175 0 948 553
451 1057 633 647 953 408 1798
306 493 466 249 97 1554 505
827 983 1640 418 896 1289 377
779 145 1759 1796 1041 627 699
7 6 1 1
1254 161 0 1601 1961 190
304 136 428 580 1350 392
1869 1230 0 0 1286 78
636 0 1932 747 64 1674
504 1103 1501 851 1049 565
0 78 1061 1399 1989 1818
1289 1570 134 491 1411 0
5 6 5 3
11 756 1233 1779 81 1320
1075 425 1724 1680 42 1481
901 600 0 484 219 1974
154 699 639 1249 570 1096
1888 1979 649 344 1750 619
5 6 4 1
200 1788 1887 35 0 1239
1034 572 433 1613 1532 733
1553 1347 0 782 1290 1850
1383 1353 1515 0 1501 531
734 0 1012 0 383 823
6 6 5 5
131 685 277 344 1256 1660
270 1442 173 788 1173 220
426 0 0 409 277 332
1841 117 1632 944 1959 263
974 1094 695 0 1974 1090
0 497 1241 1175 1065 1166
7 7 5 4
1912 869 1882 292 1642 392 0
1174 776 1720 414 1951 1712 99
1031 575 596 1240 273 803 613
0 266 345 1742 676 1293 115
818 1457 208 1687 777 0 1722
421 0 299 1192 1919 838 806
1628 1206 786 863 383 158 1573
6 5 6 3
1390 307 549 284 51
698 0 1004 810 1607
1696 475 358 670 1948
1822 539 0 383 1258
103 0 991 334 686
1133 302 729 892 694
5 6 3 6
896 755 293 1986 120 1764
0 0 1788 1295 1577 186
0 753 1404 829 382 1234
760 936 1970 0 782 844
572 849 617 824 636 0
5 5 4 5
813 0 945 1774 680
1835 704 0 1037 1039
519 214 1308 0 746
870 945 298 1972 197
1601 1454 1066 1236 0
7 6 4 5
1623 844 1418 935 0 227
1980 1405 1678 646 790 1296
1324 935 1990 1360 1359 113
1448 425 1933 2 774 1805
1713 479 1784 1385 956 862
0 631 1296 1328 1152 154
262 31 1994 516 1910 1716
7 7 3 5
243 1367 0 0 638 1370 1303
0 10 1078 480 1974 1626 0
249 1259 2001 116 0 458 1133
98 169 0 1996 784 410 444
1270 947 1510 1843 274 1915 1123
694 256 1189 1095 889 1115 0
1834 634 446 1822 482 0 306
6 6 3 2
657 1399 1730 1416 78 1448
323 903 912 526 1162 0
840 763 1454 1345 1937 508
482 1194 819 1431 1007 1087
353 1566 435 1681 1550 1120
0 1950 1149 1785 1782 469
7 5 6 1
423 0 1745 69 0
1180 787 94 1133 818
194 1577 0 1918 1978
116 981 1967 781 734
1293 316 0 1283 571
1589 359 1094 1096 1965
1463 363 1216 910 1742
7 7 6 5
1236 0 1879 1130 346 827 167
1473 1067 336 158 0 1705 17
1221 107 1492 736 1234 633 1100
1157 658 291 905 1765 1321 1457
1124 1068 1911 397 1811 550 1965
41 1739 1662 685 1245 179 964
672 295 1589 1812 1307 1035 608
6 6 3 2
0 601 1545 1029 1387 1474
0 1761 755 1619 1424 692
515 1222 1308 0 1841 1191
1599 164 0 1618 347 1492
1157 0 70 1353 1163 1031
822 0 854 788 706 1779
5 7 3 4
126 394 362 19 588 948 282
1871 1769 114 1802 157 906 785
1107 1759 670 1394 577 1720 112
0 1774 172 834 898 1167 1991
1414 102 678 1780 1596 150 1578
5 6 2 6
1260 543 0 1206 1668 1680
1281 1295 0 435 1680 1872
303 90 1246 438 1451 1051
1666 0 0 590 437 1708
1274 154 526 585 0 1684
5 6 5 4
286 145 1602 455 1708 1994
1837 183 199 465 892 44
619 724 0 0 804 1954
286 1884 1739 317 1894 382
615 271 0 738 391 1564
5 5 1 5
177 425 1430 103 1937
662 478 45 0 549
1178 0 257 1923 1545
0 1367 1924 1947 724
371 0 1289 599 854
7 7 5 5
184 1209 69 328 0 1697 66
1916 1117 1028 1985 1218 1023 546
1119 0 5 101 103 838 1041
1742 1286 853 1003 428 1038 636
918 1889 1823 1922 1805 0 1519
562 1892 1309 466 206 1652 1901
0 887 1458 1069 40 1780 0
5 6 1 4
1833 684 1687 696 840 389
1336 1223 1758 1946 406 687
1886 1982 875 544 1202 0
523 0 0 257 0 923
1390 307 583 1836 1162 1060
7 5 3 5
1338 1721 0 0 971
215 0 396 86 0
1556 449 1848 400 471
126 798 890 645 1344
67 0 1026 1958 995
1651 481 47 431 1972
761 664 1071 982 1899
5 6 5 3
225 1526 293 1171 1705 128
1966 318 61 1002 328 1425
528 1831 916 0 1280 1376
1862 0 657 0 98 1652
1249 1664 394 1036 0 300
5 7 1 3
1705 921 1008 1849 0 0 379
426 1088 448 1903 1211 1830 437
1681 180 1189 1503 1657 690 582
1085 1861 1736 1934 945 575 1120
84 113 1309 1891 868 500 1050
7 7 5 7
1341 180 2000 702 7 1925 480
1171 761 962 581 1599 951 506
1493 994 657 782 0 0 469
1743 0 221 910 1531 1686 1553
1708 742 1693 0 1642 1292 0
1155 406 1161 960 737 752 1202
834 1261 1949 1248 568 1676 305
5 7 3 6
1833 1601 1287 1229 1039 471 74
1694 690 1738 220 0 1661 1104
1894 1757 1077 1633 163 1642 1467
128 464 868 296 685 0 59
1302 1313 86 908 1494 1164 0
7 7 7 4
1000 315 947 691 1695 258 800
451 1393 738 230 1651 104 858
1815 537 1046 1485 803 479 1411
938 949 695 1233 995 1261 1908
79 1550 1245 0 0 778 1328
1042 489 768 556 0 1377 337
1014 1507 223 1190 1874 0 580
7 7 1 4
1122 0 1758 819 0 1348 1641
1974 865 44 0 0 1939 0
354 1004 28 633 1848 1716 1772
137 516 1878 1692 1116 0 1050
1894 539 1142 1114 1295 535 0
587 1200 704 0 170 1796 1137
97 0 632 297 1560 435 989
7 7 5 6
258 568 478 303 1480 1086 780
1547 454 1352 1470 757 0 1051
59 0 579 383 1124 1899 105
1661 741 1377 1221 1141 0 239
208 913 933 1038 1311 284 0
287 17 13 212 1343 1500 1690
216 1895 0 1752 1707 355 4
7 7 3 2
1170 1115 1096 1781 1377 1766 1305
718 870 928 1437 18 0 1225
189 94 171 1813 698 1656 1444
35 415 0 536 0 205 177
353 1663 0 1479 464 1982 1769
1014 47 971 297 28 1506 661
574 64 230 923 968 1225 493
7 7 4 1
1025 1312 1601 990 1855 108 1994
1308 1621 715 545 0 561 1136
14 1157 1579 493 0 746 1988
563 1705 1845 896 504 1284 843
1917 1298 207 0 1190 1514 59
993 29 162 660 705 1841 412
1986 707 18 1271 1208 1961 1059
7 7 1 2
1249 1813 1932 1143 309 136 0
0 150 1681 0 907 1207 623
1886 1060 1741 1480 248 1098 512
0 118 1813 1661 0 0 0
661 605 1532 1682 744 1168 1782
1444 331 1285 989 1763 764 1452
530 1989 1671 999 1231 314 1692
7 7 5 5
682 206 136 177 1120 540 0
1025 536 0 1171 259 648 384
1353 107 1496 1849 1883 0 623
197 667 1532 1885 1276 962 1637
260 1672 1465 612 1894 1602 1958
1625 231 1686 1675 1184 278 315
823 821 1463 878 657 1284 1853
7 7 6 7
0 1753 1390 0 1730 1661 1482
1966 1714 0 123 1997 1134 499
1829 1218 234 957 983 701 1718
1667 603 1021 1966 883 236 760
767 1536 6 704 730 1673 525
1594 1606 1329 2 35 1728 1425
770 439 1616 167 612 350 1372
7 7 1 1
451 1408 1885 0 531 0 1368
1428 1207 970 808 1091 1386 900
1912 1582 1874 172 1139 1106 0
1981 1787 0 1564 0 508 1294
1690 0 1387 610 0 911 1920
0 410 1888 1941 1361 1789 1087
813 606 1244 471 1959 469 545
7 7 1 1
282 641 731 939 573 772 1431
672 1472 89 239 978 263 0
754 1068 678 1800 673 1466 825
1187 65 1806 73 1468 1910 307
1181 1567 819 1558 1748 308 0
287 1676 757 1833 1590 1769 1323
451 1397 97 1932 578 1552 349Leave a Comment