10
1
Challenge
Given a grid like this,
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
write a piece of code that can determine the size of the largest square that does not include a '#'. (The answer to this input is 5x5 as the bottom right 5x5 grid is the biggest square possible).
The square must have sides parallel to the x and y axes.
As some small details: the original grid is always a square and its side length is given to you. The coordinates of the '#' symbols are also given to you.
Input Details
First line: N (1 <= N <= 1000), the side length of the square grid, and T (1 <= T <= 10,000) the number of '#' signs.
Next T Lines: The coordinates of each of the T #'s
Test Cases
Input #1:
8 3
2 2
2 6
6 3
Result #1: 5
================
Input #2:
8 4
1 1
1 8
8 1
8 8
Result #2: 6
================
Input #3:
5 1
3 3
Result #3: 2
This is a fastest-code problem, so the fastest code tested on the rextester compiler wins.
Have fun!
1Related. – user202729 – 2018-01-02T03:57:26.007
3For
fastest-code
1000x1000 is too small, though – l4m2 – 2018-01-02T04:07:23.3831But rextester doesn't support Jelly or Hexagony. – user202729 – 2018-01-02T04:08:48.320
@user202729 I guess you meet memory lack first – l4m2 – 2018-01-02T04:09:20.067
6
As capable as rextester is, may I recommend using try it online instead? It contains many more langauges, and is community run.
– ATaco – 2018-01-02T04:10:17.450@ATaco https://codegolf.meta.stackexchange.com/questions/12707/is-tio-acceptable-for-fastest-code-questions
– user202729 – 2018-01-02T04:11:19.117maybe TIO as pretest? – l4m2 – 2018-01-02T04:12:37.077
1"the fastest code tested on the rextester compiler wins" - fastest on what input? – Nathaniel – 2018-02-12T05:45:28.907
@user202729 rextester should have exactly the same problems. – Dennis – 2018-02-20T10:05:58.897