fork download 
  1. #include<iostream>
  2. using namespace std;
  3. int n,m,arr[100][100];
  4.  
  5. int cal_Yeven[]={-1,-1,-1,1,1,0};
  6. int cal_Yodd[]={0,-1,0,1,1,0};
  7. int cal_IYeven[]={0,-1,0,1,-1,0};
  8. int cal_IYodd[]={1,-1,1,1,-1,0};
  9. bool safe(int x,int y)
  10. {
  11. 	if(x<0 || y<0 || x>=n || y>=m) return false;
  12. 	return true;
  13. }
  14. int cal_Y(int x,int y)
  15. {
  16. 	int a,b,i;
  17. 	int val=arr[x][y];
  18. 	for(i=0;i<6;i=i+2)
  19. 	{
  20. 		if(y%2==0)
  21. 		{
  22. 			a=x+cal_Yeven[i];
  23. 			b=y+cal_Yeven[i+1];	
  24. 			if(safe(a,b)) val+=(arr[a][b]);
  25. 		}
  26. 		else
  27. 		{
  28. 			a=x+cal_Yodd[i];
  29. 			b=y+cal_Yodd[i+1];	
  30. 			if(safe(a,b)) val+=(arr[a][b]);
  31. 		}
  32. 	}
  33. 	return val;
  34. }
  35.  
  36. int cal_IY(int x,int y)
  37. {
  38. 	int a,b,i;
  39. 	int val=arr[x][y];
  40. 	for(i=0;i<6;i=i+2)
  41. 	{
  42. 		if(y%2==0)
  43. 		{
  44. 			a=x+cal_IYeven[i];
  45. 			b=y+cal_IYeven[i+1];	
  46. 			if(safe(a,b)) val+=(arr[a][b]);
  47. 		}
  48. 		else
  49. 		{
  50. 			a=x+cal_IYodd[i];
  51. 			b=y+cal_IYodd[i+1];	
  52. 			if(safe(a,b)) val+=(arr[a][b]);
  53. 		}
  54. 	}
  55. 	return val;
  56. }
  57.  
  58. int visited[1000][1000];
  59. int calE[]={-1,-1,-1,0,-1,1,0,-1,0,1,-1,0};
  60. int calO[]={-1,0,0,-1,0,1,1,-1,1,0,1,-1};
  61.  
  62. void dfs(int x,int y,int val,int &max,int number)
  63. {
  64. 	int i;
  65. 	if(number==4) 
  66. 	{
  67. 		if(max<val) max=val;
  68. 		return;
  69. 	}
  70. 	visited[x][y]=1;
  71. 	if(y%2==0)
  72. 	{
  73. 		for(i=0;i<12;i=i+2)
  74. 		{
  75. 			int a=x+calE[i];
  76. 			int b=y+calE[i+1];
  77. 			if(safe(a,b) && !visited[a][b]) 
  78. 			{
  79. 				dfs(a,b,val+arr[a][b],max,number+1);
  80. 			}
  81. 		}	
  82. 	} 
  83. 	else
  84. 	{
  85. 		for(i=0;i<12;i=i+2)
  86. 		{
  87. 			int a=x+calO[i];
  88. 			int b=y+calO[i+1];
  89. 			if(safe(a,b) && !visited[a][b]) 
  90. 			{
  91. 				dfs(a,b,val+arr[a][b],max,number+1);
  92. 			}
  93. 		}	
  94. 	} 
  95. 	visited[x][y]=0;
  96. }
  97.  
  98. int main()
  99. {
  100. 	int t;
  101. 	cin>>t;
  102. 	while(t--)
  103. 	{
  104. 	cin>>n>>m;
  105. 	int i,j;
  106. 	for(i=0;i<n;i++)
  107. 	{
  108. 		for(j=0;j<m;j++)
  109. 		{
  110. 			cin>>arr[i][j];
  111. 		}
  112. 	}
  113. 	int ans=-100;
  114. 	for(i=0;i<n;i++)
  115. 	{
  116. 		for(j=0;j<m;j++)
  117. 		{
  118. 			int val1=0;
  119. 			dfs(i,j,arr[i][j],val1,1);
  120. 			int val2=cal_Y(i,j);
  121. 			int val3=cal_IY(i,j);
  122. 			int val=max(val2,max(val1,val3));
  123. 		//	cout<<val1<<" "<<val2<<" "<<val3<<endl;
  124. 			if(ans<val) 
  125. 			{
  126. 				ans=val;
  127. 			//	cout<<"asa"<<val1<<" "<<val2<<" "<<val3<<endl;
  128. 			}
  129. 		}
  130. 	}
  131. 	cout<<ans<<endl;
  132. 	}
  133. }
Success #stdin #stdout 0s 19184KB
comments (?)
stdin 
6
3 4
150 450 100 320
120 130 160 110
10 60 200 220
1 4
10 20 30 40
3 5
300 410 150 55 370 
120 185 440 190 450 
165 70 95 420 50 
5 5
356 55 41 453 12 
401 506 274 506 379 
360 281 421 311 489 
425 74 276 371 164 
138 528 461 477 470 
3 13
197 51 443 274 47 552 160 96 501 102 469 318 308 
516 128 506 471 381 418 328 517 380 78 569 58 90 
113 238 179 444 541 27 444 62 264 93 245 353 37 
11 7
292 182 586 607 259 190 239 
511 716 425 367 511 462 714 
593 713 231 60 118 442 82 
626 577 579 682 136 176 681 
240 23 410 193 230 729 109 
453 231 287 383 444 578 409 
729 401 408 330 213 574 54 
684 224 75 62 660 472 227 
606 37 473 487 222 185 476 
84 477 158 94 141 484 122 
616 333 302 626 29 99 674
stdout 
1130
100
1500
1936
1982
2690
https://ideone.com/5LTIte
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!