armybrave

 avatar
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 349
Leave a Comment