Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cstdlib>
- #include <cmath>
- using namespace std;
- typedef long double ld;
- const int MaxN = 30;
- const ld eps = 1e-8;
- struct Point {
- int x, y;
- Point() {
- x = 0, y = 0;
- }
- Point(int X, int Y) {
- x = X, y = Y;
- }
- };
- const Point d[8] = {Point(0, 1), Point(0, -1), Point(1, 0),
- Point(1, 1), Point(1, -1), Point(-1, 0), Point(-1, 1), Point(-1, -1)};
- Point start;
- bool vis[MaxN][MaxN];
- int ma[MaxN][MaxN];
- ld g[MaxN * MaxN][MaxN * MaxN];
- int num[MaxN][MaxN];
- int i, j, k, l, n, m, r;
- char ch;
- ld ans[MaxN * MaxN], dans, mx;
- int ind[MaxN * MaxN];
- void dfs(Point v) {
- if (vis[v.x][v.y] || (v.x >= n || v.y >= m))
- return;
- vis[v.x][v.y] = 1;
- for (int i = 0; i < 8; i++)
- if ((v.x + d[i].x >= 0 && v.y + d[i].y >= 0)
- && !(ma[v.x + d[i].x][v.y + d[i].y] == 1))
- dfs(Point(v.x + d[i].x, v.y + d[i].y));
- }
- void Less(int i, int j, int ll) {
- ld kof = g[i][ll] / g[j][ll];
- for (int k = ll; k < l; k++)
- g[i][k] -= g[j][k] * kof;
- ans[i] -= ans[j] * kof;
- }
- int main() {
- cin >> n >> m;
- for (i = 0; i < n; i++)
- for (j = 0; j < m; j++) {
- cin >> ch;
- ma[i][j] = (ch == '#');
- if (ch == 'M')
- start = Point(i, j);
- if (ch == 'C')
- ma[i][j] = -1;
- }
- dfs(start);
- dans = 0;
- for (i = 0; i < n; i++)
- for (j = 0; j < m; j++)
- dans += (vis[i][j] && ma[i][j] == -1);
- if (dans == 0) {
- cout << "-1";
- return 0;
- }
- k = 1, l = 1;
- for (i = 0; i < n; i++)
- for (j = 0; j < m; j++)
- if (vis[i][j]) {
- if (ma[i][j] == -1)
- continue;
- if (num[i][j] == 0)
- num[i][j] = l, l++;
- dans = 1;
- for (int p = 0; p < 8; p++)
- if (vis[i + d[p].x][j + d[p].y]) {
- dans++;
- if (ma[i + d[p].x][j + d[p].y] == -1)
- continue;
- if (num[i + d[p].x][j + d[p].y] == 0)
- num[i + d[p].x][j + d[p].y] = l, l++;
- g[k][num[i + d[p].x][j + d[p].y]] = -1;
- }
- g[k][num[i][j]] = dans - 1;
- ans[k] = dans;
- ind[k] = k;
- k++;
- }
- for (i = 1; i < l; i++)
- ind[i] = i;
- for (i = 1; i < l; i++) {
- mx = 0;
- for (j = i; j < l; j++)
- if (fabs(g[ind[j]][i]) > mx) {
- mx = fabs(g[ind[j]][i]);
- r = j;
- }
- swap(ind[r], ind[i]);
- for (j = 1; j < k; j++)
- if (i != j && fabs(g[ind[j]][i]) > eps)
- Less(ind[j], ind[i], i);
- }
- i = num[start.x][start.y];
- cout.precision(20);
- if (g[ind[i]][i] < eps)
- cout << "=(";
- cout << ans[ind[i]] / g[ind[i]][i];
- // cin >> n;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement