armybrave
quoc14
c_cpp
17 days ago
10 kB
2
Indexable
Never
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 349
Leave a Comment