QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#690398#9224. Express Evictionucup-team902#AC ✓12ms8420kbC++232.7kb2024-10-30 21:59:512024-10-30 21:59:52

Judging History

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

  • [2024-10-30 21:59:52]
  • 评测
  • 测评结果:AC
  • 用时:12ms
  • 内存:8420kb
  • [2024-10-30 21:59:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 50 * 50 * 50;
namespace dinic {
struct edge {
    int v, p;
    long long c;
};
vector<edge> g[N];
int n;
int dis[N], cur[N];
int addv(int cnt = 1) {
    while (cnt--) g[n++].clear();
    return n - 1;
}
void adde(int u, int v, long long c) {
    g[u].push_back({v, (int)g[v].size(), c});
    g[v].push_back({u, (int)g[u].size() - 1, 0});
}
bool bfs(int s, int t) {
    fill_n(dis, n, INT_MAX);
    queue<int> q;
    q.push(t);
    dis[t] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const edge& e : g[u]) {
            int v = e.v;
            if (dis[v] != INT_MAX || !g[e.v][e.p].c) continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
    return dis[s] != INT_MAX;
}
long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    long long sf = 0;
    for (int& i = cur[u]; i != g[u].size(); ++i) {
        edge& e = g[u][i];
        int v = e.v;
        if (!e.c || dis[v] + 1 != dis[u]) continue;
        long long df = dfs(v, t, min(e.c, f));
        sf += df;
        f -= df;
        e.c -= df;
        g[v][e.p].c += df;
        if (!f) break;
    }
    return sf;
}
long long dinic(int s, int t, long long mf) {
    long long sf = 0;
    while (bfs(s, t)) {
        fill_n(cur, n, 0);
        long long f = dfs(s, t, mf);
        sf += f;
        mf -= f;
        if (!mf) break;
    }
    return sf;
}
};  // namespace dinic

string mp[55];

int id[55][55];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> mp[i];
    dinic::n = 2 * n * m + 3;
    int s = 2 * n * m + 1, t = s + 1;
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            id[i][j] = ++cnt;
            if (mp[i][j] == '#') dinic::adde(id[i][j], id[i][j] + m * n, 1);
            if (j == 0 || i == n - 1) {
                dinic::adde(s, id[i][j], 0x3f3f3f3f);
            }
            if (i == 0 || j == m - 1) {
                dinic::adde(n * m + id[i][j], t, 0x3f3f3f3f);
            }
        }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            for (int dx = -2; dx <= 2; ++dx) {
                for (int dy = -2; dy <= 2; ++dy) {
                    int xx = i + dx, yy = j + dy;
                    if (xx < 0 || xx >= n || yy < 0 || yy >= m) continue;
                    if (dx == 0 && dy == 0) continue;
                    dinic::adde(id[i][j] + n * m, id[xx][yy], 0x3f3f3f3f);
                }
            }
        }
    }
    cout << dinic::dinic(s, t, 0x3f3f3f3f) << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5616kb

input:

4 6
.##...
.#....
##....
....#.

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

20 30
...###########################
#..###########################
...###########################
...###########################
.#############################
...###########################
...###########################
#..###########################
...###########################
..#...............

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

35 35
....###########...#########........
##..#######################..#####.
....#######################..#####.
...#.....##################..#####.
.##......##################.....##.
.##..##..#############.....#....##.
.....##..#############......##..##.
....#....#############..##..##..##.
####.....

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

30 20
.#..........##......
..#......#..##......
.......#..........#.
..#......#..##......
.....#......#.......
.#.........#........
......#...#.........
..#..##..#...#......
......#.......#.....
..#....#............
........#..#.#......
....##..#...........
.........#.#.......#
........##..........
...

output:

5

result:

ok 1 number(s): "5"

Test #5:

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

input:

50 45
...##................##...................#..
...#......#.#..........#.#.....####....#....#
....#.....#..............#..#..##......##..#.
.....#......######........#.............#....
......##...#...##...##.......#....#..#...##..
...#..##.....##...###.............#..##.....#
...#......########...

output:

24

result:

ok 1 number(s): "24"

Test #6:

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

input:

50 45
...#...................#.####................
...........................#......###.#..##..
..#.#........##.##....#....#.................
.....#.....#.##.#.#.........#................
...........#.#.#.#.##....#.#.......##.#..#...
...#......#...#####......#...##.##........#..
............####.....

output:

23

result:

ok 1 number(s): "23"

Test #7:

score: 0
Accepted
time: 4ms
memory: 8420kb

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 5ms
memory: 6532kb

input:

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

output:

72

result:

ok 1 number(s): "72"

Test #9:

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

input:

50 50
..................................................
..................................................
..................................................
..................................................
..................................................
..........................................

output:

0

result:

ok 1 number(s): "0"

Test #10:

score: 0
Accepted
time: 4ms
memory: 8068kb

input:

43 50
...........#######################################
#########...######################################
#########...####....##############################
##########..#........#############################
##########...........#############################
#####.....#....####...##########......#...

output:

5

result:

ok 1 number(s): "5"

Test #11:

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

input:

8 13
.##..........
.##..#######.
.##......#.#.
...#.....#.#.
....###..#.#.
##..###..#.#.
##.......#.#.
##.......#.#.

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

36 25
##.......................
.........................
#........................
.........................
.........................
.........................
.........................
.........................
.........................
..................#.....#
..............#.#..#..#..
...........

output:

7

result:

ok 1 number(s): "7"

Test #13:

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

input:

30 20
...............#....
.#......#...#.....#.
.#...##..####..#..#.
...............#..#.
.....##.##.##.......
....#........#......
..#.#.........#.....
.#.##......#..#..##.
#.#........#........
##.#.##.....#.......
.......#.....#######
##......#.#......##.
....##..#....#..##.#
#...##..###..#...#.#
...

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

1 50
....#.#####.########.#.#...##..#..#..##.....##.#..

output:

25

result:

ok 1 number(s): "25"

Test #15:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #16:

score: 0
Accepted
time: 4ms
memory: 7916kb

input:

40 50
...###############################................
.....#############################...############.
##....############################..#############.
###...############################...############.
####...###########################...############.
#####...###########################..##...

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

8 13
.##..........
.##..#######.
.##......###.
...#.....###.
....###..###.
##..###..###.
##.......###.
##.......###.

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

10 15
...#...........
...............
.#.............
...#...........
......#.#.....#
.....#.....####
....#.....#....
...#...#.#.....
...#........#..
...##.......#..

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

50 3
.##
.#.
#..
..#
..#
#..
###
...
###
...
###
##.
...
...
##.
.#.
#..
...
##.
...
#..
..#
..#
..#
##.
..#
..#
#..
.##
...
##.
..#
...
...
###
..#
.#.
#.#
#..
.#.
###
###
#.#
#.#
###
..#
###
...
#..
..#

output:

21

result:

ok 1 number(s): "21"

Test #20:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #21:

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

input:

20 30
.....####......####...........
###..####..##..####..########.
###..####..##.....#..####..##.
.....####....#....#..####..##.
....#....#....##.....##.......
.###......##..##.....##.......
.###..##..##..#########..#####
.###..##..##..######.....#####
......##..##..######....#.....
.....#....##..#...

output:

6

result:

ok 1 number(s): "6"

Test #22:

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

input:

25 36
....###########....................#
##..#############...##########....##
....#############....########....###
...#.....#########...########...####
.##......##########....######..#####
.##..##..##########.....#####..#####
.....##..###########......###.......
....#....#############.......#........

output:

11

result:

ok 1 number(s): "11"

Test #23:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

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

output:

99

result:

ok 1 number(s): "99"

Test #25:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

4 2
#.
#.
##
..

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

4 6
.##...
.#....
##....
....#.

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

4 3
.##
###
.#.
#.#

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

2 2
.#
#.

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

25 36
....################################
##..################################
....################################
...#.....###########################
.##......###########################
.##..##..###########################
.....##..###########################
....#....##########################...

output:

10

result:

ok 1 number(s): "10"

Test #32:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #33:

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

input:

6 10
.##.....##
.##..#....
.##...#...
...#...##.
....#..##.
##.....##.

output:

2

result:

ok 1 number(s): "2"

Test #34:

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

input:

18 13
#..#..#.#..#.
...#....##.##
###...#.#....
.###...#.#.#.
...###..#.#..
..#.....####.
##...####....
..####.#.....
#####...#....
..##.##....##
.#....#..##.#
#..#......###
#.#.##...###.
#..##.......#
#.####..#...#
#.#.#...#...#
...#.#.##.###
...#.#.###..#

output:

11

result:

ok 1 number(s): "11"

Test #35:

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

input:

45 50
....#######...##################.......###........
##..#######....#################..##...###..#####.
....########...#################..##..####..#####.
...#.....###############.....###..##........#####.
.##......###############.....###....#......#....#.
.##..##..###############..#.....#....##...

output:

24

result:

ok 1 number(s): "24"

Test #36:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #37:

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

input:

45 50
....#################...############......########
##..#################...########............######
....##################...###.........####....#####
...#.....############.....#......#########...#####
.##......############..#......#############...####
.##..##..############...#..#..#########...

output:

24

result:

ok 1 number(s): "24"

Test #38:

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

input:

1 1
#

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

25 36
.....#################..............
###..#################...##########.
.....#################...##########.
....#......###########....#########.
.###.......############........####.
.###..###..#############........###.
.###..###..##################...###.
......###..###################..###...

output:

8

result:

ok 1 number(s): "8"

Test #40:

score: 0
Accepted
time: 12ms
memory: 6536kb

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #41:

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

input:

6 10
.#.....#..
....#..##.
...#...###
###...#...
.##..#....
..#.....#.

output:

2

result:

ok 1 number(s): "2"

Test #42:

score: 0
Accepted
time: 4ms
memory: 7864kb

input:

43 50
##...#............################################
######.....................#######################
###############..................#################
#########################...........##############
###############################.......############
######....................#######.........

output:

6

result:

ok 1 number(s): "6"

Test #43:

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

input:

15 10
....##....
##..##..#.
##..##..#.
....##..#.
...#....#.
.##.....#.
.##..####.
.##..####.
.....####.
....#.....
####......
####..####
......####
......####
..........

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #45:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #46:

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

input:

35 35
##.................................
.#.........................#.#.....
........#.................#....#...
...#....#...........#..............
...#.##...#............##......#...
###.#.##..#........#..#........#...
#.......##..##.#.#...##.#..##......
#.#.#.#.#..##......#.#..#....#.....
###.##...

output:

16

result:

ok 1 number(s): "16"

Test #47:

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

input:

36 25
.......................#.
#.#....#.#.##.#........#.
..#.##.#.##.#..##..#.##..
####............#..#.....
#...##.......##.#..#.....
##.##.#..#...#.#.........
.#.####..##......#.....#.
...#.##....#..........#..
##.....#....#..#..##.#...
.#......##...#.....#...#.
.#...#...#...###.......#.
.#..##.....

output:

11

result:

ok 1 number(s): "11"

Test #48:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #49:

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

input:

20 49
#..#.###.#...##..######..#..#.#.##.##....#..#.#.#
#...##..####.##.####.#.#.#.##.#.#..#.######....#.
.##.###.#.#..#####.####.#.##..###.##.####.##.#.##
...#.###....#######.#.#..#.....##.##..##.#...#.##
.##..##.###.#.....###.....#.#..##.######...######
##.#.##.#..##......###..#..#..##.##...##.###...

output:

32

result:

ok 1 number(s): "32"

Test #50:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

25 36
.......#############################
#####..#############################
#####..#############################
.......#############################
......#.......######################
.#####........######################
.#####..####..######################
.#####..####..#####################...

output:

7

result:

ok 1 number(s): "7"

Test #52:

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

input:

40 50
#################..##################...##########
#################..###############......##########
#################..############.........##########
############################........##############
########################.........#################
#####################.........#########...

output:

48

result:

ok 1 number(s): "48"

Test #53:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #54:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #55:

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

input:

3 3
.#.
###
.##

output:

3

result:

ok 1 number(s): "3"

Test #56:

score: 0
Accepted
time: 4ms
memory: 8200kb

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #57:

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

input:

20 30
...#################..........
#..#################..#######.
...#################..##......
...#################..##......
.###################..##..####
...#################..##......
...#################....#.....
#..###########......#....####.
...###########.......##..####.
..#......#####....

output:

6

result:

ok 1 number(s): "6"

Test #58:

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

input:

40 50
#.....#####...........#############.........######
####..#####.....####..############............####
###...#####...######..###########....#####.....###
###...####...####.....##########....########....##
##...#####...####....#.............##########...##
##...#####...####..##.............#####...

output:

9

result:

ok 1 number(s): "9"

Test #59:

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

input:

50 43
.#####..###################################
.####...###################################
.#####..#############......################
.##################...........#############
.################.......#.......###########
.###############......####.#.....##########
..#############....###########...

output:

6

result:

ok 1 number(s): "6"

Test #60:

score: 0
Accepted
time: 4ms
memory: 6276kb

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #61:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #62:

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

input:

50 43
....#############...#.###.##.#.............
...###...#.###......#.#..#.................
...#####.###..#..###..#.#..#...............
##########.#........#....#.................
####....#..#..##.#...#...#.#...............
####......#..##.#..#.#....#................
###.......##..#.....#..##...#....

output:

38

result:

ok 1 number(s): "38"

Test #63:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #64:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #65:

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

input:

4 6
.##...
.#....
##....
#...#.

output:

2

result:

ok 1 number(s): "2"

Test #66:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #67:

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

input:

43 50
.#################################................
##################################................
##################################..############..
##################################..############..
#..###############################..#############.
#..###############################........

output:

38

result:

ok 1 number(s): "38"

Test #68:

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

input:

15 10
..........
#########.
..........
..........
.#########
..........
..........
#########.
......###.
......###.
.###..###.
.###......
.###......
.#########
..........

output:

0

result:

ok 1 number(s): "0"

Test #69:

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

input:

11 18
##....##..####...#
##.##..##..##.#.#.
...##.#.##..#.##.#
#...########...###
..#.##.#.#.##.#.##
#####....#..###.##
.###...#.##.##.#..
#..##.#.#####..#..
####..#..####..###
#.#..###.#.##.####
.#.###.#.##.##....

output:

15

result:

ok 1 number(s): "15"

Test #70:

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

input:

36 25
.#.......................
....#####..#.#.#######...
.....############..##.##.
####.#.#.###..##.##.###..
.#####.####...........#..
#.##.##...............##.
#............#.###...###.
.#......#.#########..###.
##...##.##..##.####..###.
#...#########.....#...#..
##..#.#..##..#.##........
.#..##.#...

output:

8

result:

ok 1 number(s): "8"

Test #71:

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

input:

50 40
.#.##.##..#.#...........................
###..##.####.......#####.#####.#.#..#...
.#######.#.#....##...###.##.#.#######.#.
###.#######...###..####.########.#####..
..####.##......####.########.####.##.##.
.###..###....#####.####.#.#.##.######...
..#####.##..#.##.###.###........##..###.
.#...##...

output:

9

result:

ok 1 number(s): "9"

Test #72:

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

input:

50 43
.#......#.#..#.####..#.#.#.....#.#.#.#.....
..#....##.###.##..###.#.#..#......#..#....#
..###...#.#....##...##.....#.#######...#.##
..#......##.##....##.####..##.#.###.#.#..#.
...###.#..###....#....#.#....#.#.####..####
.....#.#..##...##..#..#..........##.#....##
....#....#####..####...#.........

output:

5

result:

ok 1 number(s): "5"

Test #73:

score: 0
Accepted
time: 4ms
memory: 6524kb

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #74:

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

input:

36 25
.......................#.
##....##.#.##.#....#.#...
....#.#..#...#....#.#....
#..#..........#......##..
.................#......#
##...........##.........#
....#.#..##...........#..
#.###.#....#.........#..#
.......#....##...#.#...##
........##......#.#.....#
.#..##...#....##...#.#.#.
#....#.....

output:

10

result:

ok 1 number(s): "10"

Test #75:

score: 0
Accepted
time: 9ms
memory: 8092kb

input:

44 50
.##.#..#.##..##......#.##.##....##.#.#####.#..####
...#.########..##..#.#.#...#.#####.#......#.#.####
.#..#...#....####..........####...####........#.##
#.#.#....#...##.##.###.#....#..###.#.....##...###.
#.######......#..#.##.##.#.....###.##..#####...##.
.....#.###...##.#.##.####...####.######...

output:

42

result:

ok 1 number(s): "42"

Test #76:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed