QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#534740#9224. Express Evictionucup-team052#AC ✓20ms6768kbC++232.2kb2024-08-27 15:47:582024-08-27 15:47:58

Judging History

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

  • [2024-08-27 15:47:58]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:6768kb
  • [2024-08-27 15:47:58]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define N 55
char s[N][N];
int n,m;
const int inf=1000000;
namespace flow
{
	const int M=2505;
	int s,t;
	struct Edge{int v,cap,nxt;};
	Edge edge[M*100];
	int fir[M*5],cur[M*5],dep[M*5],ss;
	void init() {memset(fir,0,sizeof(fir)); ss=1;}
	void addedge(int u,int v,int w)
	{
		edge[++ss]=(Edge){v,w,fir[u]}; fir[u]=ss;
		edge[++ss]=(Edge){u,0,fir[v]}; fir[v]=ss;
	}
	int bfs()
	{
		for(int i=1;i<=t;i++) dep[i]=0;
		static queue<int> q;
		dep[s]=1,q.push(s);
//		printf("%d %d\n",s,t);
		while(!q.empty())
		{
			int u=q.front(); q.pop();
			for(int i=fir[u];i!=0;i=edge[i].nxt)
			{
				if(!edge[i].cap) continue;
				int v=edge[i].v;
				if(!dep[v]) dep[v]=dep[u]+1,q.push(v);
			}
		}
		return dep[t];
	}
	int dfs(int u,int fl)
	{
		// printf("%d %d\n",u,fl);
		if(u==t||!fl) return fl;
		int ans=0;
		for(int &i=cur[u];i!=0;i=edge[i].nxt)
		{
			if(!edge[i].cap) continue;
			int v=edge[i].v;
			if(dep[v]!=dep[u]+1) continue;
			int go=dfs(v,min(fl,edge[i].cap));
			if(go)
			{
				fl-=go,ans+=go;
				edge[i].cap-=go;
				edge[i^1].cap+=go;
			}
			if(!fl) return ans;
		}
		return ans;
	}
	int dinic()
	{
		int ans=0;
		while(bfs())
		{
			for(int i=1;i<=t;i++) cur[i]=fir[i];
			ans+=dfs(s,inf);
		}
		return ans;
	}
};
using flow::addedge;
int ind[N][N],ond[N][N];
int cnt;
int gid(int x,int y) {return (x-1)*m+y;}
signed main()
{
#ifdef xay5421
	freopen("b.in","r",stdin);
#endif
	cin>>n>>m;
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	flow::init();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		ind[i][j]=++cnt,ond[i][j]=++cnt;
		addedge(ind[i][j],ond[i][j],s[i][j]=='#');
	}
	flow::s=++cnt,flow::t=++cnt;
	for(int i=1;i<=n;i++) addedge(flow::s,ind[i][1],inf);
	for(int j=1;j<=m;j++) addedge(flow::s,ind[n][j],inf);
	for(int i=1;i<=n;i++) addedge(ond[i][m],flow::t,inf);
	for(int j=1;j<=m;j++) addedge(ond[1][j],flow::t,inf);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		for(int dx=-2;dx<=2;dx++) for(int dy=-2;dy<=2;dy++)
		{
			if(dx==0&&dy==0) continue;
			int tx=i+dx,ty=j+dy;
			if(1<=tx&&tx<=n&&1<=ty&&ty<=m) addedge(ond[i][j],ind[tx][ty],inf);
		}
	}
	int ans=flow::dinic();
	cout<<ans<<endl;
	return 0;
}

詳細信息

Test #1:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #5:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #6:

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

input:

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

output:

23

result:

ok 1 number(s): "23"

Test #7:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #8:

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

input:

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

output:

72

result:

ok 1 number(s): "72"

Test #9:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #11:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #13:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #15:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #16:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #20:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #21:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #22:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #23:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

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

output:

99

result:

ok 1 number(s): "99"

Test #25:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

4 2
#.
#.
##
..

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

2 2
.#
#.

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #32:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #33:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #34:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #35:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #36:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #37:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #38:

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

input:

1 1
#

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #40:

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

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #41:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #43:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #45:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #46:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #47:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #48:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #49:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #50:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #52:

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

input:

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

output:

48

result:

ok 1 number(s): "48"

Test #53:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #54:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #55:

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

input:

3 3
.#.
###
.##

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #57:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #58:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #59:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #60:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #61:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #62:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #63:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #64:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #65:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #66:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #67:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #68:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #69:

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

input:

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

output:

15

result:

ok 1 number(s): "15"

Test #70:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #71:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #72:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #73:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #74:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #75:

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

input:

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

output:

42

result:

ok 1 number(s): "42"

Test #76:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed