도전
이와 같은 그리드가 주어지면
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
‘#’을 포함하지 않는 가장 큰 사각형의 크기를 결정할 수있는 코드를 작성하십시오. (오른쪽 하단 5×5 그리드가 가능한 가장 큰 사각형이므로이 입력에 대한 답변은 5×5입니다.)
정사각형의 변은 x 및 y 축과 평행해야합니다.
몇 가지 작은 세부 사항으로 : 원래 격자는 항상 정사각형이며 측면 길이가 제공됩니다. ‘#’기호의 좌표도 제공됩니다.
입력 세부 사항
첫 번째 줄 : N (1 <= N <= 1000), 정사각형 격자의 측면 길이, T (1 <= T <= 10,000) ‘#’부호의 수.
다음 T 라인 : 각 T #의 좌표
테스트 사례
입력 # 1 :
8 3
2 2
2 6
6 3
결과 # 1 : 5
================
입력 # 2 :
8 4
1 1
1 8
8 1
8 8
결과 # 2 : 6
================
입력 # 3 :
5 1
3 3
결과 # 3 : 2
이것은 가장 빠른 코드 문제이므로 rextester 컴파일러 에서 테스트 한 가장 빠른 코드가 우선 합니다.
즐기세요!
답변
Node.js
입력을 (w, l) 로 가져옵니다. 여기서 w 는 너비이고 l 은 좌표 배열 [x, y] 입니다. 입력 형식이 설명 된대로 엄격하면 변경 될 수 있습니다. O (w²) 에서 작동 합니다.
f = (w, l) => {
var x, y,
W = w * w,
a = new Uint16Array(W),
best = 0;
l.forEach(([x, y]) => a[(y - 1) * w + x - 1] = 1);
for(y = w; y < W; y += w) {
for(x = y + 1; x < y + w; x++) {
if(a[x]) {
a[x] = 0;
}
else {
best = Math.max(
best,
a[x] = Math.min(a[x - 1], a[x - w], a[x - w - 1]) + 1
);
}
}
}
return best;
}답변
C (gcc)
여기에는 멋진 알고리즘이 없으며 거의 무력입니다 …하지만 C는 빠릅니다.
입력 : stdin 에서 입력을 받습니다.
출력 : 출력을 stdout에 씁니다 .
#include <stdio.h>
#include <stdint.h>
int main(void) {
uint_fast16_t n, t, i, j, h, x, y, flag, biggest = 0;
scanf("%hi %hi", &n, &t);
uint_fast8_t m[n][n];
for (uint_fast16_t c = 0; c < t; ++c) {
scanf("%hi %hi", &i, &j);
m[i-1][j-1] = '#';
}
for (i = 0; i < n - 1; ++i) {
for (j = 0; j < n - 1; ++j) {
flag = 1;
for (h = 1; flag && i + h < n + 1 && j + h < n + 1; ++h) {
for (y = i; flag && y < i + h; ++y) {
for (x = j; flag && x < j + h; ++x) {
if (m[y][x] == '#') flag = 0;
}
}
if (flag && h > biggest) biggest = h;
}
}
}
printf("%d", biggest);
}