QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561061#9224. Express EvictionAfterlife#AC ✓31ms44996kbC++172.6kb2024-09-12 19:52:012024-09-12 19:52:01

Judging History

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

  • [2024-09-12 19:52:01]
  • 评测
  • 测评结果:AC
  • 用时:31ms
  • 内存:44996kb
  • [2024-09-12 19:52:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1e3+7;

struct Edge{
    int ne,to,w;
}edg[N*2+1];

int cnt=1,head[N],hd[N];

void build(int u,int v,int w)
{
    ++cnt;
    edg[cnt].to=v;
    edg[cnt].ne=head[u];
    edg[cnt].w=w;
    head[u]=cnt;
    ++cnt;
    edg[cnt].to=u;
    edg[cnt].ne=head[v];
    edg[cnt].w=0;
    head[v]=cnt;
}

queue<int> q;

int d[N],S,T;

bool bfs()
{
    fill(d+S,d+T+1,-1);
    d[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        hd[x]=head[x];
        for(int tmp=head[x];tmp;tmp=edg[tmp].ne)
        {
            int v=edg[tmp].to;
            if(d[v]!=-1||!edg[tmp].w)
                continue;
            d[v]=d[x]+1;
            q.push(v);
        }
    }
    return d[T]!=-1;
}

int dinic(int x,int mn)
{
    if(!mn||x==T)
        return mn;
    int flow=0,tmpf;
    for(int &tmp=hd[x];tmp;tmp=edg[tmp].ne)
    {
        int v=edg[tmp].to;
        if(d[v]==d[x]+1&&(tmpf=dinic(v,min(mn,edg[tmp].w)))>0)
        {
            flow+=tmpf;
            mn-=tmpf;
            edg[tmp].w-=tmpf;
            edg[tmp^1].w+=tmpf;
        }
        if(!mn)
            break;
    }
    return flow;
}

int n,m;

string s[N];

int gid(int x,int y,int i)
{
    return (x-1)*m+y+(i-1)*n*m;
}

int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,1,0,-1,-1,1,-1,1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    S=0,T=n*m*4+1;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        s[i]=' '+s[i];
    }
    //1:in 2:out 3:(0) 4:(1)
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            build(gid(i,j,1),gid(i,j,2),1e9);
            build(gid(i,j,2),gid(i,j,3),1e9);
            build(gid(i,j,3),gid(i,j,4),s[i][j]=='#');
            build(gid(i,j,4),gid(i,j,1),1e9);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int d=0;d<8;d++)
            {
                int k=i+dx[d],l=j+dy[d];
                if(k<1||k>n||l<1||l>m)
                    continue;
                build(gid(i,j,2),gid(k,l,3),1e9);
                build(gid(i,j,4),gid(k,l,1),1e9);
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]!='#')
                continue;
            if(j==1||i==n)
                build(S,gid(i,j,3),1e9);
            if(j==m||i==1)
                build(gid(i,j,4),T,1e9);
        }
    int ans=0;
    while(bfs())
        ans+=dinic(S,1e9);
    cout<<ans<<"\n";
}
/*
6 4
..#.
###.
#...
....
...#
....
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 39668kb

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #5:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #6:

score: 0
Accepted
time: 13ms
memory: 43048kb

input:

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

output:

23

result:

ok 1 number(s): "23"

Test #7:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #8:

score: 0
Accepted
time: 31ms
memory: 41792kb

input:

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

output:

72

result:

ok 1 number(s): "72"

Test #9:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #11:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #13:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #15:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #16:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #20:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #21:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #22:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #23:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

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

output:

99

result:

ok 1 number(s): "99"

Test #25:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

4 2
#.
#.
##
..

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

2 2
.#
#.

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #32:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #33:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #34:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #35:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #36:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #37:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #38:

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

input:

1 1
#

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #40:

score: 0
Accepted
time: 29ms
memory: 41356kb

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #41:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #42:

score: 0
Accepted
time: 10ms
memory: 39892kb

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #43:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #45:

score: 0
Accepted
time: 11ms
memory: 40320kb

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #46:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #47:

score: 0
Accepted
time: 11ms
memory: 42792kb

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #48:

score: 0
Accepted
time: 18ms
memory: 40492kb

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #49:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #50:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #52:

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

input:

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

output:

48

result:

ok 1 number(s): "48"

Test #53:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #54:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #55:

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

input:

3 3
.#.
###
.##

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #57:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #58:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #59:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #60:

score: 0
Accepted
time: 18ms
memory: 42528kb

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #61:

score: 0
Accepted
time: 20ms
memory: 41292kb

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #62:

score: 0
Accepted
time: 26ms
memory: 39516kb

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #63:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #64:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #65:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #66:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #67:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #68:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #69:

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

input:

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

output:

15

result:

ok 1 number(s): "15"

Test #70:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #71:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #72:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #73:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #74:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #75:

score: 0
Accepted
time: 24ms
memory: 42664kb

input:

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

output:

42

result:

ok 1 number(s): "42"

Test #76:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed