Square-free Grid 2

모든 칸을 무작위 순서로 섞고, 그 순서대로 검은색 칸을 추가한다. 칸 $(r,c)$를 추가할 때 이 칸이 새 정사각형의 꼭짓점이 되는 경우만 검사하면 된다. 거리 $d\geq1$과 다른 꼭짓점이 있는 네 방향 $(\pm d,\pm d)$를 확인한다. 나머지 세 꼭짓점이 모두 검은색인 경우에는 이 칸을 흰색으로 남긴다.

처음에는 모든 칸이 흰색이다. 검은색 칸을 추가할 때마다 새로 생기는 정사각형을 검사하므로, 완성한 격자에는 네 꼭짓점이 모두 검은색인 정사각형이 없다. 검은색 칸 수가 $13100$개보다 적으면 다른 순서로 다시 시도한다. 목표에 도달하면 격자를 출력한다.

한 번의 시도는 $O(256^3)$시간과 $O(256^2)$공간을 사용한다. 성공할 때까지 $Q$번 시도하면 총 시간 복잡도는 $O(Q\cdot256^3)$이다.

Solution written by GPT6