Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.89 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7. typedef long double ld;
  8. const int MaxN = 30;
  9. const ld eps = 1e-8;
  10. struct Point {
  11. int x, y;
  12. Point() {
  13. x = 0, y = 0;
  14. }
  15. Point(int X, int Y) {
  16. x = X, y = Y;
  17. }
  18. };
  19. const Point d[8] = {Point(0, 1), Point(0, -1), Point(1, 0),
  20. Point(1, 1), Point(1, -1), Point(-1, 0), Point(-1, 1), Point(-1, -1)};
  21.  
  22. Point start;
  23. bool vis[MaxN][MaxN];
  24. int ma[MaxN][MaxN];
  25. ld g[MaxN * MaxN][MaxN * MaxN];
  26. int num[MaxN][MaxN];
  27. int i, j, k, l, n, m, r;
  28. char ch;
  29. ld ans[MaxN * MaxN], dans, mx;
  30. int ind[MaxN * MaxN];
  31.  
  32. void dfs(Point v) {
  33. if (vis[v.x][v.y] || (v.x >= n || v.y >= m))
  34. return;
  35. vis[v.x][v.y] = 1;
  36. for (int i = 0; i < 8; i++)
  37. if ((v.x + d[i].x >= 0 && v.y + d[i].y >= 0)
  38. && !(ma[v.x + d[i].x][v.y + d[i].y] == 1))
  39. dfs(Point(v.x + d[i].x, v.y + d[i].y));
  40. }
  41.  
  42. void Less(int i, int j, int ll) {
  43. ld kof = g[i][ll] / g[j][ll];
  44. for (int k = ll; k < l; k++)
  45. g[i][k] -= g[j][k] * kof;
  46. ans[i] -= ans[j] * kof;
  47. }
  48.  
  49. int main() {
  50. cin >> n >> m;
  51. for (i = 0; i < n; i++)
  52. for (j = 0; j < m; j++) {
  53. cin >> ch;
  54. ma[i][j] = (ch == '#');
  55. if (ch == 'M')
  56. start = Point(i, j);
  57. if (ch == 'C')
  58. ma[i][j] = -1;
  59. }
  60.  
  61. dfs(start);
  62. dans = 0;
  63. for (i = 0; i < n; i++)
  64. for (j = 0; j < m; j++)
  65. dans += (vis[i][j] && ma[i][j] == -1);
  66. if (dans == 0) {
  67. cout << "-1";
  68. return 0;
  69. }
  70.  
  71. k = 1, l = 1;
  72. for (i = 0; i < n; i++)
  73. for (j = 0; j < m; j++)
  74. if (vis[i][j]) {
  75. if (ma[i][j] == -1)
  76. continue;
  77. if (num[i][j] == 0)
  78. num[i][j] = l, l++;
  79.  
  80. dans = 1;
  81. for (int p = 0; p < 8; p++)
  82. if (vis[i + d[p].x][j + d[p].y]) {
  83. dans++;
  84. if (ma[i + d[p].x][j + d[p].y] == -1)
  85. continue;
  86. if (num[i + d[p].x][j + d[p].y] == 0)
  87. num[i + d[p].x][j + d[p].y] = l, l++;
  88. g[k][num[i + d[p].x][j + d[p].y]] = -1;
  89. }
  90. g[k][num[i][j]] = dans - 1;
  91. ans[k] = dans;
  92. ind[k] = k;
  93. k++;
  94. }
  95.  
  96. for (i = 1; i < l; i++)
  97. ind[i] = i;
  98.  
  99. for (i = 1; i < l; i++) {
  100. mx = 0;
  101. for (j = i; j < l; j++)
  102. if (fabs(g[ind[j]][i]) > mx) {
  103. mx = fabs(g[ind[j]][i]);
  104. r = j;
  105. }
  106. swap(ind[r], ind[i]);
  107. for (j = 1; j < k; j++)
  108. if (i != j && fabs(g[ind[j]][i]) > eps)
  109. Less(ind[j], ind[i], i);
  110. }
  111.  
  112. i = num[start.x][start.y];
  113. cout.precision(20);
  114. if (g[ind[i]][i] < eps)
  115. cout << "=(";
  116. cout << ans[ind[i]] / g[ind[i]][i];
  117. // cin >> n;
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement