Untitled

Bao ve nong trang
Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này.
Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm N (1 < N <= 700) hàng và M (1 < M <= 700) cột. Mỗi phần tử của ma trận là độ cao H_ij so với mặt nước biển (0 <= H_ij <= 10,000) của ô (i, j). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.
Đỉnh đồi là 1 hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ X không quá 1 và chênh lệch tọa độ Y không quá 1.
[Input]
* Dòng 1: Số lượng mẫu
* Dòng 2: Hai số nguyên cách nhau bởi dấu cách: N và M
* Dòng 3: N+1: Dòng i+1 mô tả hàng i của ma trận với M số nguyên cách nhau bởi dấu cách: H_ij
[Output]
* Dòng 1: Một số nguyên duy nhất là số lượng đỉnh đồi.
[Sample]
[Input]
3
8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
8 7
4 3 2 2 1 1 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
8 7
4 3 2 2 1 1 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0
2 1 1 2 1 0 0
1 1 2 2 0 1 0
0 0 0 2 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0
 
[Output]
#1 3
#2 2
#3 1


7 294
9211 8161 6203 5226 9316 8034 5265 3288 6759 5253 2231 7644 9202 8444 3746 8449 2654 4610 9286 9079 4044 3417 9538 4198 2842 192 4476 3196 2129 1253 7478 9568 4367 4629 5319 7567 9663 3691 9907 3856 3223 8002 2510 7048 1310 5999 5467 9028 8582 1897 8537 8878 2999 3122 3150 161 7485 6580 1395 5026 4263 9248 238 6709 9415 5430 8991 5772 9609 5339 1447 1235 6496 4187 1450 9445 7893 4919 314 5210 1175 7465 5891 5045 5371 8581 8829 9037 4372 2704 6721 7604 6262 3163 5064 7138 1790 6687 4581 6007 1855 7875 7050 856 6297 5477 3815 6873 9847 3980 3836 5947 4512 5505 8608 7496 9197 5292 3680 1356 5638 3817 8249 1963 9010 2593 4073 5571 3379 3086 6471 9912 2676 5277 1036 2969 9080 8263 3421 1973 8177 8522 7552 3043 9422 196 9985 5424 752 5435 3039 9725 8653 4915 7110 8257 8432 6515 4887 4169 6694 9364 9358 7139 7030 1426 9950 2736 16 7509 4047 8808 4119 1927 458 6328 6116 7303 6976 7994 7959 5700 880 9194 6674 7367 1087 4520 764 143 3366 6002 7562 5461 2622 4516 139 4741 8527 4292 812 8861 8852 5985 6705 9439 1103 244 4657 5579 7451 4839 4995 3464 9573 1117 9857 7774 7276 2871 893 9604 6249 6929 7240 6908 2406 1112 3834 5623 5335 5626 3177 6791 8106 4315 4744 475 351 3967 7222 1337 6545 6914 6880 4970 9951 6841 4187 2746 429 114 7886 3948 4555 530 2555 8731 6756 6556 2576 9690 8685 4448 7066 7905 78 7666 3638 6528 5951 147 7532 2238 1610 7907 7055 9624 3868 8607 2358 1193 3104 8415 5604 6987 5719 731 5214 5704 147 9439 556 7069 
6641 6284 3346 7420 3801 3914 2413 1868 6859 1997 7490 7832 9436 5488 5203 8842 4315 3759 8031 6779 5050 4509 7988 57 7472 509 6878 7182 1005 9069 489 4646 2861 8795 8918 440 707 9745 4632 1990 8387 5508 1127 3901 8052 6076 7417 8212 2746 6604 8159 8840 3796 190 1279 5938 8403 9281 3362 5708 6661 3452 1331 9632 8901 1966 8442 2281 7800 9977 7481 3487 809 3772 4891 4444 6566 711 5036 2554 7263 9729 2483 15 1713 5958 9008 7556 6835 9504 5661 4150 526 1080 7488 8324 8944 2144 6304 1678 4971 3597 618 9182 6335 5422 1110 7281 6050 5014 6649 5419 7077 1788 9643 4197 1316 9407 3520 7779 670 5390 8686 4022 3255 654 2589 9206 6166 8421 2635 6377 5015 6939 1060 4443 7629 4365 7334 8456 6825 1074 1857 3958 690 1020 9017 7007 2095 2278 6515 6800 4309 222 1614 9462 7195 5501 6052 991 9287 7655 8338 9275 6253 1651 5269 3806 8251 5843 9644 1226 4841 3071 8751 8650 3558 103 694 3111 2500 2347 5580 362 5148 4412 5417 8666 1316 7302 4508 6072 2286 163 7572 4371 7994 6939 7482 6982 6555 8919 9403 7934 8696 8936 2273 8315 9915 7992 1496 7818 9886 1865 5740 9834 7593 4650 5562 6757 7996 4368 3656 5427 1507 2342 4963 8095 6573 6282 9094 288 8269 1430 4059 3894 5742 2445 5925 9497 6716 7631 8833 4868 4046 5396 1952 8481 6925 5352 2055 2184 7332 776 1479 5637 2979 376 2305 3803 5339 4111 2053 8463 7448 4838 2166 8440 3629 4366 2902 8579 87 7930 8602 4715 4775 1379 1076 7046 4833 9428 9346 737 6858 9138 5401 9531 9584 2058 1232 4120 3118 8825 
54 4896 8296 1243 1861 6703 5884 5420 9982 5641 1836 912 1996 9308 8555 1134 6842 6632 5767 8269 9050 1296 7668 8897 6743 7345 6847 4911 8782 5446 3640 1260 7518 3432 9713 1847 9711 955 5316 7975 3123 674 9497 7875 4795 9237 2260 1833 6214 7684 5900 9269 5792 3995 9579 4540 5669 7550 3465 503 8998 5675 1575 2179 1912 6426 3995 6558 3280 3866 347 7291 4632 1927 6192 1353 6110 1290 6854 5015 3108 2415 3431 878 6743 9453 6325 6592 2931 7282 5754 2604 9536 2284 5787 340 858 1908 5343 6505 433 3728 7128 2746 8985 3505 2338 7391 1082 8590 2471 9666 1262 6660 5500 4918 9875 376 4542 1050 3308 7816 480 3673 3071 6050 2063 4533 989 7055 2238 8086 8231 9409 6698 2358 596 294 6684 6436 1876 3962 5367 6428 5244 7655 47 9866 2894 7750 3155 6459 4211 6797 5521 3162 7131 5063 8966 2957 3121 19 2981 8126 4295 2462 477 9047 6071 8879 8839 1732 9249 4710 4588 8713 6649 8385 4205 5661 8367 8400 8986 3431 604 7125 7237 2434 6234 1279 7358 7990 3535 9218 2217 5252 9975 5793 5843 7265 5543 1706 8589 1884 6006 8393 3686 2702 1343 1192 1650 7403 1205 9400 3122 6009 1478 5138 7906 8910 1856 2062 1079 4382 4208 6225 6767 9146 3843 22 913 549 4998 1200 2613 9606 8579 6363 7767 9039 5013 6137 6375 8660 8522 4868 6760 6384 42 9448 1725 2249 6710 4042 1369 7571 5566 4702 2486 3134 7247 8721 571 253 5226 1820 2082 735 4345 4165 2704 1903 1583 9735 2044 5210 1612 3180 4994 8438 5284 3627 5164 7329 8800 8279 9458 5072 87 7869 73 5373 5225 9867 
407 9772 4209 2335 3135 4210 7812 4913 3260 1146 2449 406 2859 8324 2458 2262 8546 4028 8560 1096 2350 1163 942 5375 207 8720 5670 6793 6499 8893 5066 9822 2710 5369 7342 4435 761 7311 9000 9378 9603 524 8888 9339 3607 2873 800 1764 4296 2718 6330 5065 837 6841 1318 9525 977 4579 3253 9223 6411 8170 3362 6031 1369 1500 6222 9513 194 2176 6596 7107 3537 9595 974 6609 9842 9358 6658 87 9918 4544 8572 3186 8551 1134 8673 8960 2392 9490 7721 9965 763 4312 6671 6464 2935 7625 9472 2144 7898 2836 7769 172 9113 8957 4838 5430 753 6031 8705 1742 843 2431 8703 5675 7963 1107 7801 7163 227 7417 2277 5639 31 3465 3443 2107 313 9451 2293 2113 3117 2172 9567 5654 8370 5027 3736 9020 7950 7071 2787 9592 8935 7192 8279 4119 3765 638 5417 5812 1728 7500 7200 5565 4968 6918 190 6891 6109 4754 9120 9510 7654 7323 5603 3951 5523 122 9923 3387 6916 7643 7754 5066 8645 400 9779 7395 8257 6409 6789 9874 953 9736 3237 2176 3838 6967 1589 9689 8511 3401 9893 4228 2909 2277 8539 8665 9796 6484 7553 6267 2179 940 3323 1975 6351 4099 2276 8893 2399 5551 4417 7417 3447 8416 9228 8325 4045 9888 2817 9125 3472 7040 1504 3684 94 9663 1471 1783 6977 1431 6969 7450 8368 3081 6856 2739 1151 4320 8803 1790 5241 2244 5641 85 8184 1197 7784 2990 1790 6328 9979 7078 4672 7802 1256 7870 6472 6123 2841 8952 7856 8815 2194 4171 9749 4288 204 3195 8551 1829 2421 1453 1235 7642 6860 8048 4409 1073 4267 9700 6021 3858 2343 1181 8904 7632 8409 5415 9716 8737 
7394 317 4031 5919 4913 311 7490 7703 1979 7678 2667 9822 9313 2842 2730 8547 1122 422 5668 7430 5781 6414 6390 457 6154 9731 6204 2422 9280 5995 1362 4061 1594 2430 6104 6029 7934 8559 9810 9552 8161 1293 1864 7876 5999 5314 6090 609 4889 4892 4815 464 1337 875 738 60 9386 4158 8746 6761 7927 1609 4971 9857 4065 2522 6857 4093 1432 340 1282 3376 257 1544 4527 2927 8358 2384 2417 6166 7837 160 5971 8344 458 6157 1865 2029 2910 4115 9979 9308 1816 5565 9427 7400 8565 5673 3068 3137 3063 4342 9746 854 3253 1272 3095 1952 2350 5359 7152 5701 2620 9419 210 5618 6479 965 7589 6927 3256 3013 5681 390 2785 3286 4803 9326 2048 1166 1975 1196 6596 484 5153 997 5467 5873 374 4075 8649 7960 3028 2106 8443 7328 2407 6742 2774 1668 3851 2267 1872 2711 9067 4005 8458 6070 75 9036 1258 2557 1759 5 3308 1867 997 4342 2783 7417 6826 2189 7188 54 2519 6849 9187 1110 9680 1072 8100 9135 9617 1307 6741 1934 2076 3423 7389 2837 8497 8120 4782 7573 1753 1311 6588 136 8584 3820 6493 2650 8766 703 8074 8872 6884 1198 8947 9526 2052 8509 710 9363 2543 6294 7764 1743 1203 8960 6018 129 123 5228 5780 8705 1416 2884 7945 2459 8945 2393 6151 2910 1757 9881 263 4177 4695 7704 4120 5162 8328 7140 5270 6801 5211 3983 7547 2584 2649 2232 4903 1314 4683 7504 2809 9174 6327 5528 3342 2129 3650 7788 3213 3392 7171 1576 2661 1449 5611 3376 7885 1999 1269 9631 3990 615 8007 1028 1788 2046 8991 9836 9506 9272 9189 1791 9034 2282 1728 463 6966 5017 
8688 2449 8367 3038 5086 9112 1341 5861 9059 4297 5587 898 8405 7592 7265 1680 4417 4960 7470 4021 6946 3340 1834 3505 6570 8969 9760 2048 6447 6972 9846 9657 1138 3305 6233 6981 3094 9284 4591 8885 2598 9276 4970 8423 645 1369 1257 3184 9209 4953 4382 65 5781 731 2727 1838 7162 3689 4364 2928 1115 7839 925 3671 902 9915 2803 7601 708 3283 4630 9418 5343 8659 6646 3425 9759 5609 9661 273 1146 1994 2359 5930 9823 1462 2967 8773 7178 2193 3428 8224 8353 5639 4664 1610 8611 4803 2822 2992 8333 1293 1116 1688 1462 4333 8308 3622 4974 9167 2138 5633 1805 1127 8159 3081 446 7572 2346 3864 648 7000 9614 8613 280 3492 9491 655 8174 3361 1918 7763 9308 4025 4718 3132 2467 611 3381 8263 4169 2240 6843 2049 439 3824 669 9785 7132 3822 80 3955 3354 3433 1751 8963 6239 1642 5179 9466 9005 8975 8529 7340 6923 9745 9496 7596 3456 7611 5389 1744 4853 9536 8546 1331 9857 4480 183 5722 974 6864 2761 7727 1354 8161 1029 8944 3376 7502 5672 7454 8466 1474 568 8092 3364 2987 2026 2954 5576 7383 9596 7341 5341 9692 9272 9341 3821 9358 8853 6210 8296 32 6077 9787 7207 6093 437 493 7278 4660 5359 9805 2947 3915 7441 4869 7494 421 8126 9569 1058 6999 1842 767 5537 6100 8605 9996 9415 4897 5400 5343 4987 6482 7400 5110 4282 3791 8833 320 6568 6056 3136 4523 2294 580 6464 6554 3761 7634 4746 4360 1948 3730 3983 5752 4431 3689 526 6729 6997 4622 531 1445 2279 6404 4746 9167 1941 539 750 6382 2636 8416 3125 782 9419 8596 8989 3695 1907 5633 
9077 9949 8640 4989 5931 9483 9286 5981 1982 2129 7671 842 4828 9515 7477 1922 6297 1752 1413 1451 5947 5466 586 8681 8725 6025 9842 9823 2027 8911 3562 8397 816 204 4399 234 97 3805 5260 9301 8438 8404 9801 6148 173 8394 2819 6631 2928 704 82 1504 2819 3646 1162 8661 7607 3659 4016 1755 7910 8835 7796 1169 3979 4428 6364 7636 7511 7480 6169 3157 3870 9702 7531 900 735 2007 7175 3938 2915 3979 6509 4776 3964 1633 715 1076 1248 5544 9642 3215 4164 7228 666 269 1247 7488 5076 9828 2813 7504 7329 338 9190 7730 5183 2115 5115 2250 1931 2642 6838 5895 2365 4981 8333 1357 5607 3591 3247 3043 591 301 4682 9769 1173 2865 3701 692 8136 8780 8511 8536 5166 1377 9869 4813 8317 596 7386 6192 2158 9546 6856 7500 9466 8153 6409 5316 4055 1613 2198 7830 783 5481 7027 7826 4184 6580 7119 880 7033 3016 9683 5065 7518 8415 7634 2670 9186 5748 9168 3924 3173 2578 3804 7708 9014 322 5981 1734 1103 8263 3762 3392 96 7520 6409 2271 8724 1668 6905 6366 2163 8639 8101 711 6143 611 6692 6005 3329 3906 3862 1903 4927 1507 1732 7815 3995 4368 4694 8749 8311 9969 4962 5119 8327 848 7763 8489 3931 9030 6457 4724 1603 6358 737 928 1281 1736 6297 3040 8393 9538 6441 191 205 3410 4211 707 7018 376 68 6319 528 7801 2171 4000 5069 7389 5071 3295 5145 7051 5762 2561 8846 9162 3451 9786 4631 6952 356 7617 4964 7739 1769 5614 5729 7685 6273 4138 9981 5193 8111 3390 8816 9638 2797 7093 4941 818 1436 9708 5048 2036 2006 3664 3378 2147 4347 7870 



// In Practice, You should use the statndard input/output
// in order to receive a score properly.
// Do not use file input and output. Please be very careful. 

#include<iostream>

using namespace std;
int N,M;
int arr[1000][1000];
int vis[1000][1000];
int Qx[10000000];
int Qy[10000000];
int front=-1, rear=-1;
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={-1,0,1,-1,1,-1,0,1};
int cnt=0;

void push(int x, int y) {
	rear++;
	Qx[rear]=x;
	Qy[rear]=y;
}

void pop(int &x, int &y) {
	front++;
	x=Qx[front];
	y=Qy[front];
}

int bfs(int x, int y) {
	bool check=true;
	push(x,y);
	vis[x][y]=1;
	while(front<rear) {
		pop(x,y);
		for (int i=0;i<8;i++) {
			int xx=x+dx[i];
			int yy=y+dy[i];
			if(xx>=0 && xx<N && yy>=0 && yy<M) {
				if (arr[xx][yy]==arr[x][y] && vis[xx][yy]==0) {
					vis[xx][yy]=1;
					push(xx,yy);
				} else if (arr[xx][yy]>arr[x][y]) {
					check = false;
				} 
			}
		}
		
	}
	if(check) {
		cnt++;
	}
	return cnt;
} 

int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	
	ios::sync_with_stdio(false);
	
	/* 
	The freopen function below opens input.txt in read only mode and 
	sets your standard input to work with the opened file. 
	When you test your code with the sample data, you can use the function
	below to read in from the sample data file instead of the standard input.
	So. you can uncomment the following line for your local test. But you
	have to comment the following line when you submit for your scores.
	*/

	freopen("text.txt", "r", stdin);
	cin >> T;

	/*
	   Read each test case from standard input.
	*/
	for(test_case = 1; test_case <= T; ++test_case)
	{
		Answer = 0;
		/////////////////////////////////////////////////////////////////////////////////////////////
		/*
			Please, implement your algorithm from this section.
		*/
		/////////////////////////////////////////////////////////////////////////////////////////////
		cin >> N >> M;
		for(int i=0;i<N;i++) {
			for (int j=0;j<M;j++) {
				cin >> arr[i][j];
			}
		}
		front=rear=-1;
		for(int i=0;i<N;i++) {
			for (int j=0;j<M;j++) {
				vis[i][j]=0;
			}
		}
		cnt = 0;
		for(int i=0;i<N;i++) {
			for (int j=0;j<M;j++) {
				if (vis[i][j]==0) {
					bfs(i,j);
				}
			}
		}

		// Print the answer to standard output(screen).
		cout << "#" << test_case << " " << cnt << endl;
	}
	return 0;//Your program should return 0 on normal termination.
}

output
#1 36766
#2 247
#3 6917
#4 35742