QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#362131#8507. Clever Cell Choicesucup-team133#AC ✓836ms3988kbC++234.5kb2024-03-23 14:15:402024-03-23 14:15:41

Judging History

你现在查看的是最新测评结果

  • [2024-03-23 14:15:41]
  • 评测
  • 测评结果:AC
  • 用时:836ms
  • 内存:3988kb
  • [2024-03-23 14:15:40]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

struct BipartiteMatching {
    int U, V, t;
    bool solved;
    std::vector<std::vector<int>> G;
    std::vector<int> L, R, visited;

    BipartiteMatching(int U, int V) : U(U), V(V), t(0), solved(false), G(U), L(U, -1), R(V, -1), visited(U, -1) {}

    void add_edge(int u, int v) {
        assert(0 <= u && u < U);
        assert(0 <= v && v < V);
        G[u].emplace_back(v);
    }

    void shuffle() {
        static std::mt19937 mt;
        for (auto& v : G) std::shuffle(v.begin(), v.end(), mt);
    }

    int solve() {
        for (bool updated = true; std::exchange(updated, false); t++) {
            for (int i = 0; i < U; i++) {
                if (L[i] == -1) {
                    updated |= dfs(i);
                }
            }
        }
        solved = true;
        return U - std::count(L.begin(), L.end(), -1);
    }

    std::vector<std::pair<int, int>> max_matching() const {
        assert(solved);
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < U; i++) {
            if (~L[i]) {
                res.emplace_back(i, L[i]);
            }
        }
        return res;
    }

private:
    bool dfs(int u) {
        if (std::exchange(visited[u], t) == t) return false;
        for (int& v : G[u]) {
            if (R[v] == -1) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        for (int& v : G[u]) {
            if (dfs(R[v])) {
                L[u] = v, R[v] = u;
                return true;
            }
        }
        return false;
    }
};

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<string> S(N);
    cin >> S;

    vector idx(N, vector<int>(M));
    vector<int> cnt(2, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (S[i][j] == '#') continue;
            int x = (i ^ j) & 1;
            idx[i][j] = cnt[x]++;
        }
    }
    int original;
    {
        BipartiteMatching BM(cnt[0], cnt[1]);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if ((i ^ j) & 1) continue;
                if (S[i][j] == '#') continue;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (clamp(ni, 0, N - 1) != ni or clamp(nj, 0, M - 1) != nj) continue;
                    if (S[ni][nj] == '#') continue;
                    BM.add_edge(idx[i][j], idx[ni][nj]);
                }
            }
        }
        original = BM.solve();
    }
    auto calc = [&](int x, int y) {
        BipartiteMatching BM(cnt[0], cnt[1]);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if ((i ^ j) & 1) continue;
                if (S[i][j] == '#') continue;
                if (i == x and j == y) continue;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dx[d], nj = j + dy[d];
                    if (clamp(ni, 0, N - 1) != ni or clamp(nj, 0, M - 1) != nj) continue;
                    if (S[ni][nj] == '#') continue;
                    if (ni == x and nj == y) continue;
                    BM.add_edge(idx[i][j], idx[ni][nj]);
                }
            }
        }
        return BM.solve();
    };
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (S[i][j] == '#') continue;
            ans += (calc(i, j) == original);
        }
    }

    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3548kb

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

3 3
..#
...
...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

1 4
...#

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 6
#..###

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

2 5
....#
###.#

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3540kb

input:

2 6
...##.
.#.###

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

5 5
##...
##.#.
##.##
##.#.
.##..

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

6 6
...##.
#..#..
......
..#...
#...##
.#....

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

10 10
####.#...#
.#.###....
#....#..#.
.....#.#..
##.#..#.#.
..#..##...
.##.#####.
#######.##
.#.#.##..#
.#.###.##.

output:

26

result:

ok 1 number(s): "26"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3884kb

input:

10 10
..#..#.###
.#######.#
.#.####.#.
......####
#..#..#.#.
...#.###.#
#.#...#.#.
.#...#....
...#.#.#.#
...###....

output:

21

result:

ok 1 number(s): "21"

Test #12:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

15 15
#......#.#.###.
#.##...####..#.
##.....##.##.#.
#.###.#..#...##
....###.##.#.#.
.#..#.###.##.#.
######.#.####.#
.#....#..####..
.....#.###.##..
#..##.###.#####
#.##.#####..###
.#######..##.#.
##....#.##...#.
....#####.##.##
...#.#........#

output:

51

result:

ok 1 number(s): "51"

Test #13:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

15 15
###.#......#...
#.....#.#.###.#
#..#.#.###..#..
.#####.##.#..#.
...#.##.#..#.#.
#.#.###.....###
......#..##....
..##..#.#.#...#
..#..#..#......
....####...#..#
.####..#.#.##.#
###.#..#.#.#...
.#.##.##....##.
.#.#####.#..#.#
#.#.#.##.#.....

output:

61

result:

ok 1 number(s): "61"

Test #14:

score: 0
Accepted
time: 2ms
memory: 3900kb

input:

20 20
####....##.#####.##.
...####.##..#.####..
#.#.....#....##..###
###..###.#.#..#..###
##.##..#.##.####....
#...###.##.###.##...
.###...#####.##....#
#...###...##........
##.#.#.#.###.......#
#...##.##.#..##.##..
..##.##.######....##
#.#....#.##.##.##..#
##.....#..#.########
##....##.###...#....
...

output:

95

result:

ok 1 number(s): "95"

Test #15:

score: 0
Accepted
time: 2ms
memory: 3700kb

input:

20 20
.##.#.#.#..##..##.#.
..#.##.##.....##..##
.#....##...####..#..
##..###..#.#..##....
....#.##.##.###...##
.#.#.##.#..###....#.
######.#..#....#.#..
.##.###..##..##.###.
#.....#.#..#.##.#.#.
###.#####.##..#.##.#
...###.####.##...#.#
.#.....#.#.#.#..###.
#.#...#####..##.####
..####.##..##.#.#.##
...

output:

109

result:

ok 1 number(s): "109"

Test #16:

score: 0
Accepted
time: 8ms
memory: 3684kb

input:

30 30
###...###....#..#.#.#######...
.##..#.###.#.####.#...#..#.#..
.##..#######..##...#....##...#
..###..#..###...#.##.....#..##
#.#.#.#.#...###.######..#....#
###..##..###.#.###.#.####..#..
.....#...####..####..##.#.##.#
..#...######.##....#..###..###
..#####......#.#...##...#..##.
##..#.#.#.##......

output:

196

result:

ok 1 number(s): "196"

Test #17:

score: 0
Accepted
time: 7ms
memory: 3620kb

input:

30 30
######....###.#..#..###.#.##.#
.#..#...#.##..#.##...#...#####
##.#.##..##.#..###.#.#...####.
.####.###..##..#..#.#####..#.#
....##.##...#...##.####..####.
..###.##.##...##.##.###.####.#
#####......#.#...#..........#.
..#.....###..##.##..##.#.#####
..##...#.##.#.#.#..#.#.#.##...
...#.#.##..###....

output:

196

result:

ok 1 number(s): "196"

Test #18:

score: 0
Accepted
time: 22ms
memory: 3688kb

input:

40 40
......##...#.##..###.##.#.....#.#.#..#.#
#..###...####.####..###.#.#.#..#.##..##.
############.#.#...##..#...#........#.##
##.###.##########...###...####.##..#####
.###.#.##.##....##...#.##.#..#..##.#..#.
##...####.##.###.#.#.##...##..####.#####
#####..##.###.##.#.#.....####..##...##..
.#..###...

output:

290

result:

ok 1 number(s): "290"

Test #19:

score: 0
Accepted
time: 23ms
memory: 3628kb

input:

40 40
.####.####.....##.......#....########..#
.#.#....#####..#.##.###..#..#.#...##.#.#
.##.####..#.#...#.######..#.....##.#.##.
.##..##...#...#.#.#..#.###.....#..##.##.
..###.#.#....#######...#.##.##...##...#.
.##..#......##.##########.##.###..#..#.#
###.##.#.##...#.#####...###..##.#.#..###
#.###.....

output:

307

result:

ok 1 number(s): "307"

Test #20:

score: 0
Accepted
time: 61ms
memory: 3652kb

input:

50 50
#..#..###.###.####..#..#.##.#.##...#.#...########.
..#.##.##..##..##.##.##.##...#.#.####.#.##...##..#
....##.#.#..#.#.#.###...##.###.#...#.##..#..#..###
#.###.#.##.#......##...#..#..#..##..#####.##.#....
.##.####..##.#..#...##...#..#...##..##.##..#.##...
.###.#..#..####....##...#......##..#.##...

output:

488

result:

ok 1 number(s): "488"

Test #21:

score: 0
Accepted
time: 65ms
memory: 3708kb

input:

50 50
...##..#.#.##...#..##........##..###..##..#......#
.......#.#..#####.##.##.##.###.#.##.#.#..##......#
...##.##.########.##...#...#...#####...###.####.#.
#....###..###.###......##.#####..##.#...#.#...###.
#.##.##...#.#....##..##.##..##.#..####..#####.##..
.##.##.#.##...#.##.#.#....##..#..#.##.#...

output:

494

result:

ok 1 number(s): "494"

Test #22:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

1 10
.#........

output:

1

result:

ok 1 number(s): "1"

Test #23:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 11
#..........

output:

0

result:

ok 1 number(s): "0"

Test #24:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

1 21
#.......#............

output:

4

result:

ok 1 number(s): "4"

Test #25:

score: 0
Accepted
time: 0ms
memory: 3656kb

input:

2 12
..#.........
......#.....

output:

0

result:

ok 1 number(s): "0"

Test #26:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2 22
....#.................
..........#......#..#.

output:

0

result:

ok 1 number(s): "0"

Test #27:

score: 0
Accepted
time: 1ms
memory: 3600kb

input:

33 3
#..
...
...
...
.#.
...
...
...
...
.#.
...
...
...
...
..#
...
...
...
...
...
...
..#
..#
...
...
...
...
...
...
...
.#.
...
.#.

output:

3

result:

ok 1 number(s): "3"

Test #28:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

42 1
.
.
.
.
.
.
#
.
.
.
.
.
.
.
.
#
.
.
.
.
.
#
.
.
.
.
#
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

output:

11

result:

ok 1 number(s): "11"

Test #29:

score: 0
Accepted
time: 15ms
memory: 3608kb

input:

13 37
##........#..........................
....................#................
..........#.............#............
..............#.....#.....#..........
....#....#.....................##....
....#........#.........#.............
........#.......#....................
....#............##............

output:

221

result:

ok 1 number(s): "221"

Test #30:

score: 0
Accepted
time: 7ms
memory: 3640kb

input:

31 13
.....#......#
........#....
....#.#......
....#........
.............
.#.........#.
......#......
............#
..#.#......#.
.............
.......#.....
.....#.......
..#..........
.##.#........
.#..#........
..........##.
.............
...........##
............#
.............
.......#.#...
...

output:

184

result:

ok 1 number(s): "184"

Test #31:

score: 0
Accepted
time: 310ms
memory: 3620kb

input:

44 44
...................#...........#............
.#............#.#..#.#......................
...#....#.........##....#...##..............
.......#....................................
.....##...#...##..........#.................
..##.#...........#.........##........#......
.....#.....................

output:

833

result:

ok 1 number(s): "833"

Test #32:

score: 0
Accepted
time: 408ms
memory: 3736kb

input:

49 46
......##.................#....................
...#.................#.....#..#..........#.#..
#.....#...............#......##....#.....#....
..........#............##...................##
...#......#.#..............###..#..........#..
..................................#...........
...........#...

output:

956

result:

ok 1 number(s): "956"

Test #33:

score: 0
Accepted
time: 820ms
memory: 3756kb

input:

50 50
..#..#................#.#.......#.................
#...........................#..#..................
...#..............#....#...............#..........
.........#..........#........................#....
...#....#..........#..#.#................##..#....
...#.........#.#.#..................#.....

output:

1020

result:

ok 1 number(s): "1020"

Test #34:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

1 7
.......

output:

4

result:

ok 1 number(s): "4"

Test #35:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

1 10
..........

output:

0

result:

ok 1 number(s): "0"

Test #36:

score: 0
Accepted
time: 129ms
memory: 3708kb

input:

31 35
...................................
...................................
...................................
...................................
...................................
...................................
...................................
...................................
.........

output:

543

result:

ok 1 number(s): "543"

Test #37:

score: 0
Accepted
time: 140ms
memory: 3700kb

input:

33 33
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.................................
.........................

output:

545

result:

ok 1 number(s): "545"

Test #38:

score: 0
Accepted
time: 460ms
memory: 3972kb

input:

42 42
..........................................
..........................................
..........................................
..........................................
..........................................
..........................................
.......................................

output:

0

result:

ok 1 number(s): "0"

Test #39:

score: 0
Accepted
time: 836ms
memory: 3700kb

input:

47 48
................................................
................................................
................................................
................................................
................................................
................................................
...

output:

0

result:

ok 1 number(s): "0"

Test #40:

score: 0
Accepted
time: 457ms
memory: 3988kb

input:

50 50
...##.#......#....#............#...........#......
...#........#.............#.....##...#.....#.....#
.......#..#..#.#...........#...............#......
.......#........#......#.................#......#.
#....................................#...#........
........#.................#.........#.....

output:

909

result:

ok 1 number(s): "909"

Test #41:

score: 0
Accepted
time: 186ms
memory: 3740kb

input:

50 50
.##...###......#......#.......###.....#.#..#.#....
.#...#.####........#.##......#...##..#..#.........
..###..#....#.......#..##.......#...#.....#...#..#
##.#....#...#...#...##.#..##.#.#..#.......#...##..
##.#..#........#.#..#.##.....#..##.....##..#...#..
.............#..#....##.....#..##.....#...

output:

688

result:

ok 1 number(s): "688"

Test #42:

score: 0
Accepted
time: 71ms
memory: 3696kb

input:

50 50
#....#.####.###........##.#...#......#..##.##.##..
#####.#.#.######..##.###.....#.#.#...#.###.#.#....
.#.#####.#..##.#...#....#.##...#.##..####.#.#...##
#.#...##..##....#....######.##.####...#.##.##.####
#..###.....#.##..###...###.##...#..####....##.##.#
#....#.#...#.##...###..###....#.###..#....

output:

536

result:

ok 1 number(s): "536"

Test #43:

score: 0
Accepted
time: 16ms
memory: 3928kb

input:

50 50
#####.#####.###..###..#######.##.#.####.#.#.###.##
###.#.####.##...##.#.##.##..####.######.#..###.#..
###...####.########..###.###.###..###.#####..#####
###########..##.###..#..#####..#....##..######.#.#
#######.####.#.#####.#...######..#.#####.#.#######
####.#.##.#######..######.##.###.##.###...

output:

371

result:

ok 1 number(s): "371"

Test #44:

score: 0
Accepted
time: 6ms
memory: 3632kb

input:

50 50
..##.####.#..#.##..#.#.#####..####.########.###.##
###.###..#.##.##..########...#########..##########
#########.#######.###..####################..#####
#######.##.###.###.###.#..####.#####...###..###.#.
##.#.##############.###########.####...##########.
.....#.#.#####.#...#.##################...

output:

299

result:

ok 1 number(s): "299"

Test #45:

score: 0
Accepted
time: 2ms
memory: 3684kb

input:

50 50
############.########################.###########.
####.##########.#############.#############.######
#####.#######.###############.#############.#.##.#
..#.##.#####..###.###########.########.####.######
###############.#.########.##############.######..
######.#################.#..##.########...

output:

189

result:

ok 1 number(s): "189"

Test #46:

score: 0
Accepted
time: 205ms
memory: 3760kb

input:

43 44
.................#....#..#...............##.
....#..#.............................#......
.............#.....................#.#......
.#.....#......#...............#.............
#...............#...#...............#.......
.#.....#..#...........#.......#.............
..#........................

output:

776

result:

ok 1 number(s): "776"

Test #47:

score: 0
Accepted
time: 19ms
memory: 3624kb

input:

15 49
.##..#........#....#....##.....#..#.......##...#.
...#.....##....##...#.#...........#..#.........#.
#..#.........##.....#.#..#.....#.#.#..#......#...
.................#...........#.....#...........#.
..#..#.....##...#......#....#.....#........#..#..
#.#.......#..........#..#...#..................

output:

218

result:

ok 1 number(s): "218"

Test #48:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

5 10
#..#......
.#....##..
..###...##
..#...#..#
#....#....

output:

3

result:

ok 1 number(s): "3"

Test #49:

score: 0
Accepted
time: 112ms
memory: 3664kb

input:

49 49
#.#.##...#.....#..##..##..##....##..###....##.##.
####.#....#......##.........##...##......#.#...##
..#...#.##....#......###...##..#.##.#.......##.#.
.....###..#....#.##.#....####..##..#..##....#..#.
#####..#...#....#.######......#..#....###..#.###.
.#.#.....###..#...#..#..#####...#.##......#....

output:

530

result:

ok 1 number(s): "530"

Test #50:

score: 0
Accepted
time: 3ms
memory: 3828kb

input:

22 22
###.#.#######.###.##.#
..###.##...#.#.#..#..#
.####.####.###.#.....#
#####..#.##.###..#.#..
###.#.#.#.#...###.###.
...###....##..##.....#
.#..##.#......#.#..#.#
.###.##.#.....#...#.#.
##..#.#######.##...#..
##...###...##.#..#####
##.#..##.##....##.###.
..#.##...##.###.##.##.
#####.##.#.#.#.##....

output:

105

result:

ok 1 number(s): "105"

Test #51:

score: 0
Accepted
time: 1ms
memory: 3860kb

input:

13 31
.###..##.#..##.#..#.#..#.###..#
.#...######....##.####.#..#.###
##..##..######...#.#####..#####
###.######.#..#.#.##..##.###.#.
##############.###..###.##.#.#.
##..##...#..#..#####.##.##....#
.###.#.##..#.....#...#..##.##.#
####.##.....######.##.#.##.#..#
...####.#.###.###.##.#..#.#.#..
..#..#...

output:

56

result:

ok 1 number(s): "56"

Test #52:

score: 0
Accepted
time: 3ms
memory: 3680kb

input:

33 33
#.###.##..####.##.##..#.##..#####
#.#.####.##.####.#####.##.####.##
#####...#.##.###########.#.####.#
###.##....##.#######.####.#######
##################.##..#######..#
##.###.#.###.##########.###.##..#
.#..#####.#####.#####.####..#.###
.##.#.###.####.#####.####.###.##.
.###.#..############.#...

output:

160

result:

ok 1 number(s): "160"

Test #53:

score: 0
Accepted
time: 487ms
memory: 3636kb

input:

50 50
......#.....................................######
......#.....................................#.....
......#.....................................#.....
......#.....................................#.....
......#.....................................#.....
......#...................................

output:

267

result:

ok 1 number(s): "267"

Test #54:

score: 0
Accepted
time: 426ms
memory: 3696kb

input:

50 50
......#..#....###.....#.#......#..................
..#....#......#...................................
.###..........#...#.....#......#.....#...#.##.....
#.........#...#.....#.............................
#.............#..#..#.....#.....#.........##......
..............#..#....#....#........#.....

output:

862

result:

ok 1 number(s): "862"

Test #55:

score: 0
Accepted
time: 258ms
memory: 3768kb

input:

50 50
...#..............#.........#.......#........#....
.........#.#.#..#...............#.#..............#
.............#...#....##......#.#..............#..
.#.#...#.......##...........##...#....#...........
.#.#....#..#.......#.#....#.#...........#.........
..##.......#..........#...#.#....#.#......

output:

926

result:

ok 1 number(s): "926"

Test #56:

score: 0
Accepted
time: 330ms
memory: 3640kb

input:

50 50
............................................#.....
............................................#.....
............................................#.....
............................................#.....
............................................#.....
..........................................

output:

406

result:

ok 1 number(s): "406"

Test #57:

score: 0
Accepted
time: 457ms
memory: 3984kb

input:

50 50
.........#########################################
..................................................
..................................................
..................................................
###################################...............
..................................#.......

output:

664

result:

ok 1 number(s): "664"

Test #58:

score: 0
Accepted
time: 304ms
memory: 3736kb

input:

50 50
.#........................................#.#.##..
.#........#...............................#...##..
##........................................#...##..
.#.......................#.............#..#...##..
###########################################...##..
..........................................

output:

650

result:

ok 1 number(s): "650"

Test #59:

score: 0
Accepted
time: 222ms
memory: 3900kb

input:

50 50
..#...#.....#.........#...#.#....#..#...#.........
............#..#...#....##.........#....#..#......
............#.......#..................##....#####
...#........#................#..........#....#..#.
............#....#.##........#....#.....#....#....
...##...#...###########################...

output:

939

result:

ok 1 number(s): "939"

Test #60:

score: 0
Accepted
time: 38ms
memory: 3864kb

input:

50 50
.#######..####.....##..#....#.#.##.####...#..#...#
#.##..###.####.###.#.........####.##....#.....##..
##.#.##..####.####.##.##..#...#.#......###.#..##..
###..#.#..#####.#####....####...#.#########...#.#.
.#.###.##.###...##.##..#.##.#...#..#.###.######..#
###..##..###..#.#..#.####.#..###.#..#.....

output:

429

result:

ok 1 number(s): "429"

Test #61:

score: 0
Accepted
time: 385ms
memory: 3632kb

input:

50 50
..##................................#..#.....#....
..##................................#..#.....#....
..##................................#..#.....#....
..#####.............................#..#.....#....
..##..#.............................#..#.....#....
..##..#.............................#.....

output:

0

result:

ok 1 number(s): "0"

Test #62:

score: 0
Accepted
time: 290ms
memory: 3740kb

input:

50 50
.............................#......#...#...#.....
.............................#......#...#...#.....
.............................#......#...#...#.....
.............................#......#...#...#.....
.............................#......#...#...#.....
.............................#......#.....

output:

264

result:

ok 1 number(s): "264"

Test #63:

score: 0
Accepted
time: 279ms
memory: 3688kb

input:

50 50
.........#..#....................##..#......#.....
.........#..#....................##..#......#.....
.........#..#....................##..#......#.....
.........#..#....................##..#...#..#.....
.........#..#....................##..#......#.....
.........#..#....................##..#....

output:

763

result:

ok 1 number(s): "763"

Test #64:

score: 0
Accepted
time: 155ms
memory: 3600kb

input:

50 50
.....#....#.###.#.....#...........................
.....#....#.###.#.....#......................#####
.....#....#.###.#.....############################
.....#....#.###.#####...#.........................
.....#....#.###.#...#...#.........................
.....#....#.###.#...#...#.................

output:

365

result:

ok 1 number(s): "365"

Test #65:

score: 0
Accepted
time: 161ms
memory: 3660kb

input:

50 50
..........................................##.#.#..
..........................................##.#.#..
############################################.#.#..
..#.........#................#............##.#.#..
..#.........#................#............##.#.#..
#############................#............

output:

301

result:

ok 1 number(s): "301"

Extra Test:

score: 0
Extra Test Passed