fork(7) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef vector<int> vi;
  4. typedef vector<vi> vvi;
  5. typedef pair<int,int> ii;
  6.  
  7. void print(vvi& v){
  8. 	for(auto it:v){
  9. 		for(auto jt:it)
  10. 			cout<<jt<<" ";
  11. 		cout<<endl;
  12. 	}
  13. }
  14.  
  15. int getDiamon(vvi& mat){
  16. 	int n = mat.size();
  17. 	vvi dm(n,vi(n,INT_MIN));	
  18. 	if(mat[0][0]==-1)return 0;
  19. 	dm[0][0] = mat[0][0]==1 ? 1:0;
  20.  
  21. 	for(int i=1;i<n;i++){
  22. 		if(mat[0][i]!=-1 && mat[0][i-1]!=-1)
  23. 			dm[0][i] = mat[0][i]==1 ? dm[0][i-1]+1 : dm[0][i-1];			
  24. 	}
  25.  
  26. 	for(int i=1;i<n;i++){
  27. 		if(mat[i][0]!=-1 && mat[i-1][0]!=-1)
  28. 			dm[i][0] = mat[i][0]==1 ? dm[i-1][0]+1 : dm[i-1][0];			
  29. 	}
  30.  
  31. 	for(int i=1;i<n;i++){
  32. 		for(int j=1;j<n;j++){
  33. 			if(mat[i][j]!=-1 && (dm[i-1][j]!=INT_MIN || dm[i][j-1]!=INT_MIN)){				
  34. 				dm[i][j] = mat[i][j]==1 ? 1+max(dm[i][j-1],dm[i-1][j]) : max(dm[i][j-1],dm[i-1][j]);
  35. 			}
  36. 		}
  37. 	}
  38. 	//print(dm);
  39.  
  40. 	//now modify original matrix to reduce diamonds
  41. 	int c = n-1, r = n-1;
  42. 	while(c>0 && r>0){
  43. 		if(mat[r][c]==1)
  44. 			mat[r][c] = 0;
  45. 		if(dm[r-1][c]>=dm[r][c-1])
  46. 			r--;
  47. 		else if(dm[r-1][c]<dm[r][c-1])
  48. 			c--;
  49. 	}
  50. 	while(c!=0){
  51. 		if(mat[r][c]==1)
  52. 			mat[r][c] = 0;
  53. 		c--;
  54. 	}
  55. 	while(r!=0){
  56. 		if(mat[r][c]==1)
  57. 			mat[r][c] = 0;
  58. 		r--;
  59. 	}
  60. 	if(mat[0][0]==1)mat[0][0]=0;
  61. 	return dm[n-1][n-1];
  62. }
  63.  
  64.  
  65. int main() {	
  66. 	int n;cin>>n;
  67. 	vvi mat(n,vi(n));
  68. 	for(int i=0;i<n;i++){
  69. 		for(int j=0;j<n;j++){
  70. 			cin>>mat[i][j];
  71. 		}
  72. 	}
  73. 	int diam = getDiamon(mat);	
  74. 	cout<<"diamonds in first iteration = "<<diam<<endl;
  75. 	cout<<"After first iteration matrix is"<<endl;
  76. 	print(mat);
  77. 	diam += getDiamon(mat);	
  78. 	cout<<"total diamonds collected are = "<<diam<<endl;
  79. 	cout<<"After second iteration matrix is "<<endl;
  80. 	print(mat);
  81. 	return 0;
  82. }
Success #stdin #stdout 0s 3420KB
comments (?)
stdin
copy 
3
1 1 0
1 1 1
1 1 1
stdout
copy 
diamonds in first iteration = 5
After first iteration matrix is
0 0 0 
1 0 0 
1 1 0 
total diamonds collected are = 8
After second iteration matrix is 
0 0 0 
0 0 0 
0 0 0
https://ideone.com/zbTtMp
max diamonds
language:
C++14 (gcc 8.3)
created:
10 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!