fork(2) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define endl '\n'
  5.  
  6. void rotate(vector<vector<char> > &matrix, int n)
  7. {
  8. 	reverse(matrix.begin(),matrix.end());
  9. 	for(int i=0;i<n;i++)
  10. 	{
  11. 		for(int j=i+1;j<n;j++)
  12. 		{
  13. 			int temp = matrix[i][j];
  14. 			matrix[i][j] = matrix[j][i];
  15. 			matrix[j][i] = temp;
  16. 		}
  17. 	}
  18. }
  19.  
  20. int findSquare(vector<vector<char> > matrix, int n)
  21. {
  22. 	vector<vector<int> > dp(n,vector<int>(n,0));
  23. 	for(int i=0;i<n;i++)
  24. 	{
  25. 		for(int j=0;j<n;j++)
  26. 		{
  27. 			if(i==0 || j==0)
  28. 			{
  29. 				if(matrix[i][j] == 'D')
  30. 				{
  31. 					dp[i][j] = 1;
  32. 				}
  33. 				else
  34. 					dp[i][j] = 0;
  35. 			}
  36. 			else if(matrix[i][j]=='D')
  37. 				dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
  38. 			else
  39. 				dp[i][j] = 0;
  40. 		}
  41. 	}
  42. 	int max = 0;
  43. 	for(int i=0;i<n;i++)
  44. 	{
  45. 		for(int j=0;j<n;j++)
  46. 		{
  47. 			if(dp[i][j]>max)
  48. 				max = dp[i][j];
  49. 		}
  50. 	}
  51. 	return max;
  52. }
  53.  
  54.  
  55.  
  56. int findAns(vector<vector<char> > matrix, int n)
  57. {
  58. 	for(int i=0;i<n;i++)
  59. 	{
  60. 		int count = 0;
  61. 		for(int j=0;j<n;j++)
  62. 		{
  63. 			if(matrix[j][i] == 'D')
  64. 			{
  65. 				count++;
  66. 			}
  67. 		}
  68. 		for(int j=0;j<count;j++)
  69. 		{
  70. 			matrix[j][i] = 'D';
  71. 		}
  72. 		for(int j=count;j<n;j++)
  73. 		{
  74. 			matrix[j][i] = 'C';
  75. 		}
  76. 	}
  77. 	return findSquare(matrix,n);
  78. }
  79.  
  80.  
  81. int main() {
  82. 	int n;
  83. 	cin>>n;
  84. 	vector<vector<char> > matrix(n,vector<char>(n));
  85. 	for(int i=0;i<n;i++)
  86. 	{
  87. 		for(int j=0;j<n;j++)
  88. 		{
  89. 			cin>>matrix[i][j];
  90. 		}
  91. 	}
  92. 	int ans1 = findAns(matrix,n);
  93. 	rotate(matrix,n);
  94. 	int ans2 = findAns(matrix,n);
  95. 	rotate(matrix,n);
  96. 	int ans3 = findAns(matrix,n);
  97. 	rotate(matrix,n);
  98. 	int ans4 = findAns(matrix,n);
  99. //	cout<<ans1<<" "<<ans2<<" "<<ans3<<" "<<ans4<<endl;
  100. 	cout<<max(max(ans1,ans2),max(ans3,ans4));
  101. 	return 0;
  102. }
  103.  
Success #stdin #stdout 0s 4552KB
comments (?)
stdin
copy 
4
C D C D
C C D C
D D D D
C D D D
stdout
copy 
3
https://ideone.com/4n2jGd
language:
C++14 (gcc 8.3)
created:
3 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!