QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#648489#9224. Express EvictionArgharizaAC ✓17ms5248kbC++143.5kb2024-10-17 19:16:002024-10-17 19:16:09

Judging History

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

  • [2024-10-17 19:16:09]
  • 评测
  • 测评结果:AC
  • 用时:17ms
  • 内存:5248kb
  • [2024-10-17 19:16:00]
  • 提交

answer

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define R(i, x, y) for (int i = (x); i >= (y); i--)
#define FIO(FILE) freopen(FILE".in", "r", stdin), freopen(FILE".out", "w", stdout)

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int inf = 1e9;

struct Flow {
	int n, s, t, tot;
	struct edge { int to, nxt, w; };
	vector<int> hd, cr, d;
	vector<edge> e;
	Flow () { }
	Flow (int _n) : n(_n), tot(-1) { hd.resize(n + 5, -1), d.resize(n + 5, 0), e.clear(); }
	void add_edge(int u, int v, int w) { e.eb((edge) { v, hd[u], w }), hd[u] = ++tot; }
	void add_flow(int u, int v, int w) { add_edge(u, v, w), add_edge(v, u, 0); }
	bool bfs() {
		fill(d.begin(), d.end(), 0);
		queue<int> q; q.push(s), d[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = hd[u]; ~i; i = e[i].nxt) {
				int v = e[i].to;
				if (!e[i].w || d[v]) continue;
				d[v] = d[u] + 1, q.push(v);
			}
		}
		return d[t];
	}
	int dfs(int u, int in) {
		if (u == t) return in;
		int out = 0;
		for (int &i = cr[u]; ~i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].w && d[v] == d[u] + 1) {
				int res = dfs(v, min(in, e[i].w));
				in -= res, out += res;
				e[i].w -= res, e[i ^ 1].w += res;
			}
			if (!in) break;
		}
		if (!out) d[u] = 0;
		return out;
	}
	int dinic() {
		FlowBack();
		int mf = 0;
		while (bfs()) cr = hd, mf += dfs(s, 1e9);
		return mf;
	}
	void FlowBack() {
		for (int i = 0; i < tot; i += 2)
			e[i].w += e[i ^ 1].w, e[i ^ 1].w = 0;
	}
	vector<bool> cut() {
		queue<int> q; vector<bool> vs; 
		vs.resize(n + 5, 0), q.push(s), vs[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (int i = hd[u]; ~i; i = e[i].nxt) {
				int v = e[i].to;
				if (!vs[v] && e[i].w && d[v] == d[u] + 1) 
					vs[v] = 1, q.push(v);
			}
		}
		return vs;
	}
	vector<tu> cutree(vector<int> S) {
		if (S.size() == 1) return vector<tu>();
		s = S[0], t = S[1]; int w = dinic();
		vector<tu> res; res.eb(mt(s, t, w));
		vector<int> sl, sr;
		auto vs = cut();
		for (int i : S) 
			if (!vs[i]) sl.eb(i);
			else sr.eb(i);
		auto tl = cutree(sl), tr = cutree(sr);
		for (tu i : tl) res.eb(i);
		for (tu i : tr) res.eb(i);
		return res;
	}
	vector<tu> cutree() {
		vector<int> S;
		for (int i = 1; i <= n; i++) S.eb(i);
		s = 1, t = 2;
		return cutree(S);
	}
};

const int N = 55;

int n, m, ct;
int id[N][N];
char c[N][N];

void solve() {
	cin >> n >> m;
	F (i, 1, n) {
		cin >> (c[i] + 1);
		F (j, 1, m) 
			if (c[i][j] == '#') id[i][j] = ++ct;
	}
	Flow G(ct * 2 + 2); G.s = ct * 2 + 1, G.t = ct * 2 + 2;
	F (i, 1, n) {
		F (j, 1, m) {
			if (id[i][j]) {
				G.add_flow(id[i][j], id[i][j] + ct, 1);
				if (j == 1 || i == n) G.add_flow(G.s, id[i][j], inf);
				if (i == 1 || j == m) G.add_flow(id[i][j] + ct, G.t, inf);
				F (dx, -2, 2) {
					F (dy, -2, 2) {
						int x = i + dx, y = j + dy;
						if (x == i && y == j) continue;
						if (x < 1 || y < 1 || x > n || y > m) continue;
						if (id[x][y]) G.add_flow(id[i][j] + ct, id[x][y], inf);
					}
				}
			}
		}
	}
	cout << G.dinic() << '\n';
}

bool Med;
int main() {
	// FIO("");
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #3:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #4:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #5:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #6:

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

input:

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

output:

23

result:

ok 1 number(s): "23"

Test #7:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #8:

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

input:

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

output:

72

result:

ok 1 number(s): "72"

Test #9:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #10:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #11:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #12:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #13:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #14:

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

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #15:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #16:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #17:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #18:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #19:

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

input:

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

output:

21

result:

ok 1 number(s): "21"

Test #20:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #21:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #22:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #23:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #24:

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

input:

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

output:

99

result:

ok 1 number(s): "99"

Test #25:

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

input:

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

output:

0

result:

ok 1 number(s): "0"

Test #26:

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

input:

4 2
#.
#.
##
..

output:

2

result:

ok 1 number(s): "2"

Test #27:

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

input:

1 1
.

output:

0

result:

ok 1 number(s): "0"

Test #28:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #29:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #30:

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

input:

2 2
.#
#.

output:

1

result:

ok 1 number(s): "1"

Test #31:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #32:

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

input:

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

output:

29

result:

ok 1 number(s): "29"

Test #33:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #34:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #35:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #36:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #37:

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

input:

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

output:

24

result:

ok 1 number(s): "24"

Test #38:

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

input:

1 1
#

output:

1

result:

ok 1 number(s): "1"

Test #39:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #40:

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

input:

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

output:

43

result:

ok 1 number(s): "43"

Test #41:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #42:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #43:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #44:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #45:

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

input:

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

output:

22

result:

ok 1 number(s): "22"

Test #46:

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

input:

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

output:

16

result:

ok 1 number(s): "16"

Test #47:

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

input:

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

output:

11

result:

ok 1 number(s): "11"

Test #48:

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

input:

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

output:

27

result:

ok 1 number(s): "27"

Test #49:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #50:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #51:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #52:

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

input:

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

output:

48

result:

ok 1 number(s): "48"

Test #53:

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

input:

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

output:

49

result:

ok 1 number(s): "49"

Test #54:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #55:

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

input:

3 3
.#.
###
.##

output:

3

result:

ok 1 number(s): "3"

Test #56:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #57:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #58:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #59:

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

input:

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

output:

6

result:

ok 1 number(s): "6"

Test #60:

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

input:

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

output:

32

result:

ok 1 number(s): "32"

Test #61:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #62:

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

input:

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

output:

38

result:

ok 1 number(s): "38"

Test #63:

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

input:

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

output:

50

result:

ok 1 number(s): "50"

Test #64:

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

input:

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

output:

31

result:

ok 1 number(s): "31"

Test #65:

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

input:

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

output:

2

result:

ok 1 number(s): "2"

Test #66:

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

input:

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

output:

13

result:

ok 1 number(s): "13"

Test #67:

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

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: 4040kb

input:

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

output:

15

result:

ok 1 number(s): "15"

Test #70:

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

input:

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

output:

8

result:

ok 1 number(s): "8"

Test #71:

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

input:

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

output:

9

result:

ok 1 number(s): "9"

Test #72:

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

input:

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

output:

5

result:

ok 1 number(s): "5"

Test #73:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #74:

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

input:

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

output:

10

result:

ok 1 number(s): "10"

Test #75:

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

input:

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

output:

42

result:

ok 1 number(s): "42"

Test #76:

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

input:

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

output:

19

result:

ok 1 number(s): "19"

Extra Test:

score: 0
Extra Test Passed