Ctrl K

Снять фишки с общей линией

Средняя
На клетчатом поле стоят фишки, tokens[i] = [x, y] — координаты i-й фишки; в одной клетке не больше одной фишки. За один ход можно снять с поля любую фишку, если в той же строке (тот же x) или в том же столбце (тот же y) стоит хотя бы одна другая фишка, ещё не снятая. Порядок ходов выбираете вы. Верните наибольшее число фишек, которые удастся снять.
Пример 1
tokens=[[0, 0], [0, 3], [2, 3], [5, 5]] → 2

Фишка (0, 0) делит строку с (0, 3), а (0, 3) — столбец с (2, 3). Снимаем (2, 3) (рядом в столбце (0, 3)), затем (0, 3) (рядом в строке (0, 0)). Фишки (0, 0) и (5, 5) остаются одни — итого 2.

Пример 2
tokens=[[1, 1], [2, 2], [3, 3]] → 0

Никакие две фишки не стоят в одной строке или столбце, снять нельзя ничего.

Пример 3
tokens=[[4, 1], [4, 7], [9, 7], [9, 1]] → 3
Ограничения
  • 1 ≤ len(tokens) ≤ 1000
  • 0 ≤ x, y ≤ 10⁴
  • Все координаты различны
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОткрытые комнаты от холла СредняяГруппы по общим меткам СредняяКого вылечить первым СложнаяКого отключить от сети СложнаяСкладываются ли связи в дерево Средняя
загружаем Python…
Вход
tokens=[[0, 0], [0, 3], [2, 3], [5, 5]]
Ожидается
2

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 99 тестов на сервере, включая скрытые.