Kiss the girls
Statement
Goal
At an HxW rave, Bob wants to kiss as many girls as possible without his odds of catching monkeypox exceeding 40%. The chances of catching monkeypox from any given girl at position (x,y) are min(x, y) / (x^2 + y^2 + 1).Input
Line 1: H W
Next H lines: The grid values (G indicates a girl), where (0,0) is the upper left corner.
Next H lines: The grid values (G indicates a girl), where (0,0) is the upper left corner.
Output
The maximum number of girls Bob can kiss.
Constraints
4 ≤ H,W ≤ 50
Example
Input
6 6 G....G .G..G. ..GG.. ..GG.. .G..G. G....G
Output
8
Tags
Difficulty
Easy
Test cases
Test 1 Test
Input
6 6
G....G
.G..G.
..GG..
..GG..
.G..G.
G....G
Output
8
Validator 1 Validator
Input
7 7
G.....G
.G...G.
..G.G..
...G...
..G.G..
.G...G.
G.....G
Output
9
Test 2 Test
Input
8 12
GGGGGGGGGGGG
G....GG....G
G....GG....G
G....GG....G
G....GG....G
G....GG....G
G....GG....G
GGGGGGGGGGGG
Output
33
Validator 2 Validator
Input
8 12
GGGGGGGGGGGG
G....GG....G
G....GG....G
GGGGGGGGGGGG
GGGGGGGGGGGG
G....GG....G
G....GG....G
GGGGGGGGGGGG
Output
35
Test 3 Test
Input
15 10
..........
..........
..........
..........
....GG....
....GG....
....GG....
....GG....
....GG....
....GG....
....GG....
....GG....
..........
..........
..........
Output
10
Validator 3 Validator
Input
15 10
..........
..........
..........
GGGGGGGGGG
..........
..........
GGGGGGGGGG
GGGGGGGGGG
GGGGGGGGGG
..........
..........
GGGGGGGGGG
..........
..........
..........
Output
21
Test 4 Test
Input
20 40
G.GG..G.GGG..G.GG.G.GGGG....GG.GGG...GGG
GGGG..GGGGG.GG.G.G.GG.GG..G....G.GG..G.G
G...GG.GG.GG.GGGGGGGG.GGGGGGGGGG.GGGGG..
GGGG.GG.GG..G.GGG..GG..GGG.GGG.G.G.GGGG.
GG..G.G.GG.GGGGGG...G.G..G.GG.G..GG.G..G
G.GGG.....GGGGGG...GGGGG..GG..GGGG.GGGG.
GG..GGGGGGGGGG.GGGG.GGGGGGGGGGG.GGGGGGGG
G.GG....G.GGG..GGGG.GGGGGGGGGG..G.GG.GGG
.G.G.GG..GGGGGGGGGG.G.GG.GGG.GGGGG..GGGG
GGGGGGGGGGGG..GGGGGGGGGG....GG.GGGGGGGGG
.GGGG.G.GGGGG.GGGGGGG..GG.GG.G...GG.G..G
GG..GGGGGGGGG.GG..G.G.G..GGG.GG..GGGGG..
GGGG.G..GGGGGGGGGGG.GG.G.G..GG.GG.G.GGG.
GGGG..GGGGGGG.GGG.GGGGG.GGGG.GG.GGG...GG
GGGGG.G.G.G...GGGG..G.G.GG...G.G.G.G.G.G
GGGGG.GGGGGG.G.G.GGG.GGGG.GGG.GG..GGGGGG
GGGGG.GGGGGGG.GGGGGGGG.GG.G.GGGG.G.GGGGG
G.G.GGGG..G...GG.GGG.GGGGG.GG.GGGG.GGG..
GGGGGG.GGGG.G..G..GG.GG.GGGG.GGGGG.GG.GG
.GGGGGGGGGGGGGGG.G.GGGG...G..GG..GGGGGGG
Output
151
Validator 4 Validator
Input
20 40
................G.......G.G...G..G.G..G.
...........G..................GG....G..G
...........G..G........G.G.G.....G......
..GG....................G.G........G.G..
....G......G.........G.....G..GGG.G..G..
G...G.......G.........G.GG..G.....G.G.G.
GG....GG......G........G.............G.G
G......GG........G.G...G....G...........
G............G......G..GG.......G.......
.....G........G.........GG........GGG...
G..GG........G.G....G..GGG........GGG...
.G..G....G..............................
..G...G......G.....G.G......G.G.......GG
...G.G...G.......G.................G....
....GGGG.G.....G.G.G..G....G.G..........
...G.....G...GG..............G..G......G
.G........G.......G...GG...G......GG..G.
..................GGG...G.G............G
...G........G.....GG....G.G..........G..
....G.........G...G...G...G.............
Output
78
Test 5 Test
Input
50 50
GG..G.....G.........GGGG.G..GG..G..G..G........G..
.......GG..G....G.G....GG.G........GG.....G.......
.......G.....G...G....................G.........GG
.....GG.....G..........GGG........G..G.G...G.G.G..
.GG.G.............G....G..G.GG....GG...G.....G....
G..G...GGG...G....G.G...G.G.G...G......GG...GG....
..G.....G.G.G...G.....G..G........................
.........GG.G...G.G.G...G........GGG.....G....G...
..G.G.......G............G.......G...........G.G..
.G.G..G..................G..G...GG...G....GGG.....
.......GG...G.....G......G.....G......G....G..G..G
.G.......GGG.G....GG..G........G..G.G.......G.G.G.
......G.......G...GG..........G..G..G.........G..G
.....G.......G.....G.....G..G........G.GGG..G.....
...G.....G..G.G.....G...........GG...........G..G.
........G..G......G.GG....G...G...G...G.G.GG......
.....G....G.........G.GG....G....G................
G......G.....GG.....G.G......G.....G..G......G....
........G.GG..GG........G.........GGG.G......G....
....G..G....G..G..................G..G.GG.........
...G....G...G....G...GG...................G....GGG
..................G......G..GG.....GG.......G.....
G.....G.G......GG.G.G...........G.................
.G......G.......G.......GGGG..........G.......GG..
......G...........G..G.G..G.G..........G.GG.G.....
......GG.G.....G..G.GG.........G....G..G....G.GGG.
..G.GG.............G.G.GG....G...G...GG.G.G.......
G.......G.G........G....G...G..G..GGGG........G..G
...GG.........GG.....GG..G......GG....G..GG....G..
.....G..G...G.............G....G.GG........G.G....
GG....GG............G..G.G...........GGG....G.....
.........G.GG.G.....G..G................G.G.......
..............G..G..............G..G.....G....GG..
..............G......G......G............G..G.....
.GG....G..G...................GG..GG..G..G........
G.G.GG..G..GG...G..G...G.....GG.....GG.G.....G..G.
....GG.....G.............G....G.GGG....G.........G
G........G.G...G...G...G.......GG.GG..G.G.G..G...G
GG.....G........G.......G..........G...G......GG..
......GG......G.....G..................G.....G....
.G.G..GG............GG....GG.G....GGG...G...G.....
...G.....G...G....G...............GG..........G..G
.........GGG......G.....G.G....G.G................
GG..G.G...G..G.G...................G..............
......GG.........G.G...G.........GG...G.........GG
........G.....G.G..G..G.....GG.................G..
G.........G..G....G.G..G...G..GG.......G.....G....
G.G...G..G.GG.G.GG...G..........G.G......G..G.....
..........G.....G...G.......G...GG.G....GG....G..G
G...G..G...G............G.G.........G..........G..
Output
150
Validator 5 Validator
Input
50 50
G.G.GG.G..GG....G.G..GGGG.G.G.GG...GG.GG.GG..GG...
.GG.GGG.G.G..G.GG.GG.GG.GG..GGGGG....G..G.GG.G..GG
GG....G.GGGGG.G..........G.G.GGG.G..GG.G.GGGGGG.G.
GG.G.....GG..GG..G.G.G....GG..G...GG.....G.GGG.G.G
.G.GGG....GGG..GG.G..GGG.G.GGG.GGGG.GGG.G.GGGGGGGG
..G.GGG...GGGGGG..GG....G.GGGG.G...G...G.G..GG.GGG
.....G...GGG..GG..GG.GGGG..G.GGG.G....G.GG.GGGG.G.
..GG.GG...G.G.G.G...GG.G.GG.G.G..G...G.G...G......
G...GGG.G.GGGGGGG..GGG.G.GGG....G....GGGGGGG.G.G..
.G.G.G.G....G..G...GG.....G...GG..G.G.GG..G.G..G.G
G....G....G..G.G.GG..G.GG....G.GGG.GGGGGG.GGG.GGGG
.G.GG.GG..G.GG.G.G.G..GGGGGG..G....G..GGGGG..G..GG
GGGGGG....GG.G.GGG.G..GGGG.....GGGGGG..G..GG.GGGG.
G.GG.GG.GGGG..GG.GG.G.GGG.G..G.G.......G.GG.GG...G
.GGGG.GGG.GG.G.G...G..GG.GG...G..G...GG.GG.G.GG.GG
GG.GG.GGGGG..GG.GG.G.....GGG.GGGG......G.GGG...GG.
..GGGGG......G.GG.G..GG..GG.G.G..G....G.G.G.GG.G.G
GG..G.G.G...G.G.G...G...GGG.....GG......G.G.G.G.GG
.GGG.G.G.GGGG....G...G..GG..G.GG.GG...G..G..G..GG.
GG.GG.GG.G..GG...G..G.GGG.G.GG...G..G.GG..GGG..GG.
.G..GGGGG..G..G.G.G..G.G.GG.....G.G.G..GGGG...G.GG
..G...G.GGGG.GGG...GG..G.GG..G.GGG.GGGG..G.G.G.GG.
..GGGG..GG.GGG...GG.G..G.GGG.G.G..G.G.GGG.G....GG.
..G.GGGGGGG.GG..GGG.G.G....G...GG.GG...GGG...GGG..
...G.G.G...G..GG...G.GGG..G...GGGGGG.G...GG...G..G
.GGGG.G.GG.....G...G..GG.G..GGG.GGGGGGG........G..
.GGGG...GGGGG.GG.GGGGGGG.G..G.GGG.G.GG.GGG...G.GGG
GGG....GGG....G...G.G.G.G....GGGG....GGGG..GGG..GG
GGG.GG.G.GG.G.....GG...G.GGGG.GG..G.G..GGGGG.GGGGG
GG....GGGGG.GG.G.GGGGGG.GG.G...G.G......GG.GGGGG.G
..G..GG.GG......G.GGG..G......GG...G....G.G.G.GGGG
.G..G.GGG.G.....G.G..GGGG...GG..G..G.G...G.G.GGGGG
GG.GG.G..GG..G.G..G..G..G.GG..G.GGGG.GG..GGGG.GGG.
..GG......GG.G...G.GGGG..G.GGGGG.G.GG....GG.G..GG.
G.G.G..GG..G.GGG....G.GGG..G....GGG.GG.G.GG.GG.GGG
G..G..GGG.GGGG.G.GGGGG.GG.GGG.....G..G.GG.....GG..
GG..G...G..G.GGG.GGG.G..GGGGG..GGGGGGG..GG..G.G.GG
GGG..GG..G.G.G.G.GG.G.G..GG..GG..G.G..GG..GGG.GGG.
.GGGG.G.....G.G..GG....G..GGG...GG.G...GG.G...G..G
.G...G.GG.G..G.GGG.GGGG.GGGGGGGG..GG..GGGGG.GGG.G.
GGG.GG..G.....GGGGG..GG.G..G.G.G..GGGG.GG.GGGGGG..
..G....G.G.G.G..G.G..GG.GG..G.G..GG..G.G....G.GGG.
...GG..GG.GGG..G.G.G...GG.GG.GGGGGGGG.GG..G.....G.
GG.GG.....G.G....GG.GG.G.GG..GG.GGGG....G..G...G.G
GGGG.GGGG.G.G.G..G..G.G.......G.G.G..GG.G...G.GGG.
.GG.G....GG.GGGG.G...G..GG.G.GGGGG.G.GGGGG...G.G.G
G.G.G.G.G.G.GG..GG.G.GG..GG.G.G.GG.......GG....GG.
.G.G.....GGGG..GGG.G..G..G.G.G.G.G....G..G.....GGG
..GG..G..G.GG...G.GGG.G.G...G.G..GG...GGG.G...G..G
G.G.G.G.GG..G.G..G.G.GG.GG.G..G..G.GG.......G....G
Output
240
Solution language
Solution
Stub generator input