JavaScript (ES6), 127 124 119 байт
Сэкономлено 3 байта благодаря nderscore
&f % Input (implicit). Push vectors of row and column indices of nonzero entries
J* % Multiply by imaginary unit
+ % Add the two vectors. Gives a vector of complex coordinates
4XN % Matrix of combinations of these complex numbers, taken 4 at a time. Each
% row is a combination
! % Transpose
" % For each column
@ % Push current column: candidate set of four points
&- % All pair-wise differences
| % Absolute value
u % Unique entries
n3= % Does the number of elements equal 3? Gives true (1) or false (0)
vs % Concatenate vertically with previous accumulated result, and sum
% End (implicit). Display (implicit)
Как?
Эта функция выполняет итерацию по всем парам ячеек. (х, у), (Х, Y) входной матрицы м такой, что:
- м[ х, у ] = м[ Х, Y ] = 1
- х < х
- y ≤ Y
Каждая совпадающая пара описывает координаты потенциального края квадрата. Неравенства гарантируют, что каждое ребро проверяется только один раз.
Мы используем вектор [ dx, dy ] = [ X - x, Y - y ] повернут на 90° по часовой стрелке, чтобы проверить ячейки, расположенные в [ х - dy, y + dx ] и [ X - dy, Y + dx ]. Если они оба содержат 1, мы нашли правильный квадрат.
Тестовые случаи
&fJ*+4XN!"@&-|un3=vs
||answer||
МАТЛ, 20 байт
let f =
m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n
console.log(f([
[0,0,0,1,0,0,0],
[1,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,0,0,1,0,0],
[0,1,0,0,0,0,0]
]));
console.log(f([
[1,0,1,0,1],
[0,0,0,0,0],
[1,0,1,0,0],
[0,0,0,0,0],
[1,0,0,0,1]
]));
console.log(f([
[1,1,1,1],
[1,1,1,1],
[1,1,1,1],
[1,1,1,1]
]));
Входные данные — матрица.
Попробуйте онлайн!
Как это работает
Это находит все координаты ненулевых записей во входной сетке и представляет их как комплексные числа, так что индексы строк и столбцов соответствуют действительным и мнимым частям соответственно.
Затем код генерирует массив всех комбинаций (порядок не имеет значения) этих чисел, взятых по 4 за раз. Каждая комбинация представляет собой квадрат-кандидат. Для каждой комбинации вычисляется матрица попарных абсолютных разностей 4×4 (т.е. расстояний в комплексной плоскости). Это симметричная матрица с нулями вдоль главной диагонали. Текущая комбинация образует квадрат тогда и только тогда, когда матрица содержит ровно 3 различных значения (это будут сторона квадрата, диагональ квадрата и ноль):
С другой стороны, например, неквадратный прямоугольник будет иметь 4 различных значения (две стороны, одно значение диагонали и ноль);
а общий четырехугольник может иметь до 7 значений (четыре стороны, две диагонали и ноль):
m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n
![[Ксения Шокина] Система кнопка. Нажми и кассуй каждый день (2018)](/assets/images/icons/forum7.png){kind=icon}
![[Джеймс Маккена, Джанин Глайста, Мэтт Фонтейн] Твой первый миллион. Как его заработать и не потерят](/assets/images/icons/forum5.png){kind=icon}
