fork download 
  1. #include<stdio.h>
  2. #include<algorithm>
  3. int l, r, u, d;
  4. char A[21][21];
  5. int dx[4] = { 1,-1,0,0 };
  6. int dy[4] = { 0,0,1,-1 };
  7. int acnt[256];
  8. bool is_gone[21][21], ck[256];
  9. bool flag[22][22][22][22];
  10. void dfs_f(int l, int r, int u, int d) {
  11. 	if (l > r || u > d || flag[l][r][u][d])return;
  12. 	flag[l][r][u][d] = 1;
  13. 	dfs_f(l + 1, r, u, d); dfs_f(l, r - 1, u, d);
  14. 	dfs_f(l, r, u + 1, d); dfs_f(l, r, u, d - 1);
  15. }
  16. struct lrud { int l, r, u, d, S; }Q[22 * 22 * 22 * 22];
  17. bool sort_S(lrud a, lrud b) { return a.S > b.S; }
  18. void dfs(int x, int y) {
  19. 	is_gone[x][y] = 1;
  20. 	for (int i = 0; i < 4; i++) {
  21. 		int nx = x + dx[i];
  22. 		int ny = y + dy[i];
  23. 		if (nx < l || r < nx || ny < u || d < ny)continue;
  24. 		if (A[nx][ny] != A[x][y] || is_gone[nx][ny])continue;
  25. 		dfs(nx, ny);
  26. 	}
  27. }
  28. int main() {
  29. 	int n, i, j, ans = 0, qn = 0;
  30. 	scanf("%d", &n);
  31. 	for (i = 0; i < n; i++)scanf("%s", A[i]);
  32. 	for (l = 0; l < n; l++)for (u = 0; u < n; u++)for (r = n - 1; r >= l; r--)for (d = n - 1; d >= u; d--) {
  33. 		Q[qn++] = { l,r,u,d,(r - l + 1)*(d - u + 1) };
  34. 	}
  35. 	std::sort(Q, Q + qn, sort_S);
  36. 	for (int q = 0; q < qn; q++) {
  37. 		l = Q[q].l, r = Q[q].r, u = Q[q].u, d = Q[q].d;
  38. 		if (flag[l][r][u][d])continue;
  39. 		int cnt = 0;
  40. 		char Q[26] = { 0, };
  41. 		for (i = l; i <= r; i++)for (j = u; j <= d; j++) {
  42. 			if (!ck[A[i][j]])Q[cnt++] = A[i][j];
  43. 			ck[A[i][j]] = 1;
  44. 			if (!is_gone[i][j])dfs(i, j), acnt[A[i][j]]++;
  45. 		}
  46. 		if ((cnt == 2 && acnt[Q[0]] == 1 && acnt[Q[1]] >= 2) || (cnt == 2 && acnt[Q[1]] == 1 && acnt[Q[0]] >= 2)) {
  47. 			ans++;
  48. 			dfs_f(l, r, u, d);
  49. 		}
  50. 		for (i = l; i <= r; i++)for (j = u; j <= d; j++) {
  51. 			is_gone[i][j] = ck[A[i][j]] = acnt[A[i][j]] = 0;
  52. 		}
  53. 	}
  54. 	printf("%d", ans);
  55. 	return 0;
  56. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin 
4
ABBC
BBBC
AABB
ABBC
stdout 
2
https://ideone.com/6Vk2tW
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!