QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#544158#9224. Express EvictionAshbourneAC ✓17ms7160kbC++143.1kb2024-09-02 10:39:352024-09-02 10:39:37

Judging History

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

  • [2024-09-02 10:39:37]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:7160kb
  • [2024-09-02 10:39:35]
  • 提交

answer

#include<bits/stdc++.h>
const int N = 10005;
const int INF = 0x3f3f3f3f;
using namespace std;
int s, t, tot, cnt;
struct Edge{
        int next, to, cap, flow; 
}edge[N * 100];
int head[N];
void add(int u, int v, int w, int rw = 0){
        edge[++tot] = {head[u], v, w, 0};
    head[u] = tot;
    edge[++tot] = {head[v], u, 0, 0};
        head[v] = tot;
}
int maxflow = 0;
int dep[N], cur[N];
bool bfs(){
        queue<int> q;
        memset(dep, 0, sizeof (dep[0]) * (cnt + 1));
        dep[s] = 1;
        q.push(s);
        while(q.size()){
                int u = q.front();
                q.pop();
                for(int i = head[u]; i; i = edge[i].next){
                        int v = edge[i].to;
                        if((!dep[v]) && (edge[i].cap > edge[i].flow)){
                                dep[v] = dep[u] + 1;
                                if(v == t) return 1;
                                q.push(v);
                        }
                }
        }
        return 0;
}
int dfs(int u, int flow){
        if((u == t) || (!flow)) return flow;
        int ret = 0;
        for(int &i = cur[u]; i; i = edge[i].next){
                int v = edge[i].to, d;
                if(dep[v] != dep[u] + 1) continue;
                d = dfs(v, min(flow - ret, edge[i].cap - edge[i].flow));
                if(d){
                        ret += d;
                        edge[i].flow += d;
                        edge[i ^ 1].flow -= d;
                        if(ret == flow) return ret;
                }
        }
        return ret;
}
void dinic(){
        while(bfs()){
                memcpy(cur, head, sizeof (head[0]) * (cnt + 1));
                maxflow += dfs(s, INF);
        }
}
int  n, m, a[55][55];
void solve(){
        memset(head, 0, sizeof head);
        tot = 1;
        cin >> n >> m;
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= m; ++ j){
                char ch; cin >> ch;
                if(ch == '#') a[i][j] = 1;
            }
        s = 1; t = 2;
        maxflow = 0;
        // I have deleted some codes about building the graph
        for(int i = 1; i <= n; ++ i)
            for(int j = 1; j <= m; ++ j){
                int tem = (i - 1) * m + j + 2;
                //cout << tem << endl;
                add(tem, tem + n * m, 1);
                if(!a[i][j]) continue;
                for(int dx = i - 2; dx <= i + 2; ++ dx)
                    for(int dy = j - 2; dy <= j + 2; ++ dy){
                        if(dx < 1 || dy < 1 || dx > n || dy > m || !a[dx][dy])continue;
                        int now = (dx - 1) * m + dy + 2;
                        if(tem < now) add(now + n * m, tem, INF), add(tem + n * m, now, INF);
                    }
                if(i == n || j == 1) add(s, tem, INF);
                if(i == 1 || j == m) add(tem + n * m, t, INF);
            }
        cnt = 2 + 2 * n * m;
        dinic();
        cout << maxflow << endl;
}
int main(){
        ios::sync_with_stdio(false);
        int T = 1;
        // cin >> T; 
        while(T--){
                solve();
        }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #5:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #6:

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

input:

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

output:

23

result:

ok 1 number(s): "23"

Test #7:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 17ms
memory: 4780kb

input:

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

output:

72

result:

ok 1 number(s): "72"

Test #9:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #11:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #13:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #15:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #16:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #20:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #21:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #22:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #23:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #24:

score: 0
Accepted
time: 14ms
memory: 6096kb

input:

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

output:

99

result:

ok 1 number(s): "99"

Test #25:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

4 2
#.
#.
##
..

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

2 2
.#
#.

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #32:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #33:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #34:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #35:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #36:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #37:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #38:

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

input:

1 1
#

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #40:

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

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #41:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #43:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #45:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #46:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #47:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #48:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #49:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #50:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #52:

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

input:

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

output:

48

result:

ok 1 number(s): "48"

Test #53:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #54:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #55:

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

input:

3 3
.#.
###
.##

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #57:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #58:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #59:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #60:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #61:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #62:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #63:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #64:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #65:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #66:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #67:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #68:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #69:

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

input:

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

output:

15

result:

ok 1 number(s): "15"

Test #70:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #71:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #72:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #73:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #74:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #75:

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

input:

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

output:

42

result:

ok 1 number(s): "42"

Test #76:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed