fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <typename T> void setmax(T& a, T b) { if (b > a) a = b; }
  5.  
  6. using i64 = int64_t;
  7.  
  8. const int MOD = 1e9 + 7;
  9.  
  10. const int MAXN = 1010;
  11. const int MAXM = 1010;
  12. int N, M;
  13. char G[MAXN][MAXM];
  14.  
  15. const int MAXV = MAXN * MAXM;
  16. int V;
  17. int par[MAXV];
  18. int ways[MAXV];
  19. void reset() {
  20. 	for (int v = 0; v < V; v++) {
  21. 		par[v] = -1;
  22. 		ways[v] = 1;
  23. 	}
  24. }
  25. int getPar(int a) {
  26. 	return par[a] < 0 ? a : (par[a] = getPar(par[a]));
  27. }
  28. void merge(int a, int b) {
  29. 	a = getPar(a), b = getPar(b);
  30. 	if (a == b) return;
  31. 	if (a > b) swap(a, b);
  32. 	ways[a] = i64(ways[a]) * ways[b] % MOD;
  33. 	par[b] = a;
  34. }
  35.  
  36. int vert(int i, int j) {
  37. 	return i * M + j;
  38. }
  39.  
  40. int main() {
  41. 	ios::sync_with_stdio(0), cin.tie(0);
  42. 	cin >> N >> M;
  43. 	for (int i = 0; i < N; i++) {
  44. 		cin >> G[i];
  45. 	}
  46.  
  47. 	V = N * M;
  48. 	reset();
  49.  
  50. 	for (int i = N-1; i >= 0; i--) {
  51. 		for (int j = 0; j < M; j++) {
  52. 			if (i+1 < N && G[i][j] == '.' && G[i+1][j] == '.') {
  53. 				merge(vert(i, j), vert(i+1, j));
  54. 			}
  55. 			if (j+1 < M && G[i][j] == '.' && G[i][j+1] == '.') {
  56. 				merge(vert(i, j), vert(i, j+1));
  57. 			}
  58. 		}
  59.  
  60. 		for (int j = 0; j < M; j++) {
  61. 			if (G[i][j] == '.' && getPar(vert(i, j)) == vert(i, j)) {
  62. 				ways[vert(i, j)]++;
  63. 			}
  64. 		}
  65. 	}
  66.  
  67. 	int ans = 1;
  68. 	for (int i = 0; i < N; i++) {
  69. 		for (int j = 0; j < M; j++) {
  70. 			if (G[i][j] == '.' && getPar(vert(i, j)) == vert(i, j)) {
  71. 				ans = i64(ans) * ways[vert(i, j)] % MOD;
  72. 			}
  73. 		}
  74. 	}
  75. 	cout << ans << '\n';
  76.  
  77. 	return 0;
  78. }
  79.  
Success #stdin #stdout 0s 4448KB
comments (?)
stdin 
4 9
#########
#...#...#
#.#...#.#
#########
stdout 
9
https://ideone.com/209nvl
language:
C++14 (gcc 8.3)
created:
4 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!