fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fo(i, n) for (int i = 0; i < int(n); i++)
  3. #define of(i, n) for (int i = int(n) - 1; i >= 0; i--)
  4. #define Fo(i, l, r) for (int i = int(l); i < int(r); i++)
  5. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  6. #define all(a) (a).begin(), (a).end()
  7. #define sz(a) int((a).size())
  8. #define pb(a) push_back(a)
  9. #define mp(x, y) make_pair((x), (y))
  10. #define x first
  11. #define y second
  12. #define endl '\n'
  13. #define deb(x) cout << #x << " " << x << endl;
  14. using namespace std;
  15.  
  16. const int N = 101;
  17. int A[N][N], B[N][N], C[N][N];
  18. int dp[N][N];
  19. int n;
  20. void solve() {
  21. 	cin >> n;
  22. 	bool f = 1;
  23. 	fo(i, n) fo(j, n){
  24. 		char c; cin >> c;
  25. 		if(c == 'C' || c == 'c') A[i][j] = 1;
  26. 		if(c == 'D' || c == 'd') f = 0;
  27. 	}
  28. 	if(f){
  29. 		cout << "0";
  30. 		return;
  31. 	}
  32. 	vector<int> col(n, 0), row(n, 0);
  33. 	fo(i, n) fo(j, n){
  34. 		col[i] += A[j][i];
  35. 		row[i] += A[i][j];
  36. 	}
  37. 	// fo(i, n) cout << row[i] << " " << col[i] << endl;
  38. 	fo(i, n) fo(j, n){
  39. 		B[i][j] = 1;
  40. 		C[i][j] = 1;
  41. 	}
  42. 	fo(j, n){
  43. 		of(i, n){
  44. 			if(col[j] > 0){
  45. 				B[i][j] = 0;
  46. 				col[j]--;
  47. 			}
  48. 			else break;
  49. 		}
  50. 	}
  51. 	fo(i, n){
  52. 		fo(j, n){
  53. 			if(row[i] > 0){
  54. 				C[i][j] = 0;
  55. 				row[i]--;
  56. 			}
  57. 			else break;
  58. 		}
  59. 	}
  60. 	int mxB = 0, mxC = 0;
  61. 	fo(i, n) fo(j, n) dp[i][j] = 0;
  62. 	fo(i, n) dp[i][0] = B[i][0];
  63. 	fo(j, n) dp[0][j] = B[0][j];
  64. 	fo(i, n) fo(j, n){
  65. 		if(i == 0 || j == 0){
  66. 			mxB = max(mxB, dp[i][j]);
  67. 			continue;
  68. 		}
  69. 		if(B[i][j] == 1){
  70. 			dp[i][j] = min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
  71. 			mxB = max(mxB, dp[i][j]);
  72. 		}
  73. 		else dp[i][j] = 0;
  74. 	}
  75. 	fo(i, n) fo(j, n) dp[i][j] = 0;
  76. 	fo(i, n) dp[i][0] = C[i][0];
  77. 	fo(j, n) dp[0][j] = C[0][j];
  78. 	fo(i, n) fo(j, n){
  79. 		if(i == 0 || j == 0){
  80. 			mxC = max(mxC, dp[i][j]);
  81. 			continue;
  82. 		}
  83. 		if(C[i][j] == 1){
  84. 			dp[i][j] = min(dp[i][j - 1], min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
  85. 			mxC = max(mxC, dp[i][j]);
  86. 		}
  87. 		else dp[i][j] = 0;
  88. 	}
  89. 	cout << max(mxB, mxC);
  90. 	// cout << endl;
  91. 	// cout << mxB << " " << mxC << endl;
  92. 	// fo(i, n){
  93. 	// 	fo(j, n){
  94. 	// 		cout << B[i][j] << " ";
  95. 	// 	}
  96. 	// 	cout << endl;
  97. 	// }
  98. 	// cout << endl;
  99. 	// fo(i, n){
  100. 	// 	fo(j, n){
  101. 	// 		cout << C[i][j] << " ";
  102. 	// 	}
  103. 	// 	cout << endl;
  104. 	// }
  105. }
  106.  
  107. int main() {
  108.     int t = 1;
  109.     while (t--) {
  110.         solve();
  111.     }
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
5
C D D C D
C D D C C
C C C C D
D D C C D
D D D D D
stdout
copy 
2
https://ideone.com/uFTjn0
language:
C++ (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!