Відремонтуйте ставок

Ферма креветок використовує прямокутний ставок, побудований у вигляді сітки з $2N$ рядків і 2N+1 стовпців квадратних клітин, для заданого цілого числа $N$. Кожна сторона клітини має довжину один метр. Ставок містить точно (2N-1) \times N бар'єрів довжиною два метри, які використовуються для тимчасової ізоляції менших ділянок всередині ставка для розведення різних видів креветок. Бар'єри мають свої середні точки, зафіксовані точно на цілих координатах $(a,b)$, для всіх 0 < a < 2N і 0 < b < 2N+1, де обидва $a$ і $b$ є непарними, або обидва парними. Кожен бар'єр може обертатися навколо своєї середньої точки, щоб змінити конфігурацію ставка; однак, при обертанні, бар'єр перемикається лише між двома можливими положеннями, завжди паралельними до сторін ставка, вертикальним або горизонтальним. Ліва частина малюнка нижче показує конфігурацію ставка, з N = 3.

Наприкінці кожного сезону ставок закривається для технічного обслуговування та очищення. Потім його потрібно переконфігурувати так, щоб спеціальна машина могла підмести дно ставка. Машина починає свою роботу з верхньої лівої клітини і повинна пройти через кожну клітину рівно один раз, закінчуючи в нижній лівій клітині. Права частина малюнка показує одну таку переконфігурацію, де шість бар'єрів були перемкнуті. Для цього прикладу, однак, чотири перемикання бар'єрів було б достатньо.

Ви повинні написати програму, яка, маючи конфігурацію ставка, визначає мінімальну кількість перемикань бар'єрів, необхідних для переконфігурації ставка, як зазначено вище. Завжди є принаймні один можливий спосіб переконфігурувати ставок, як зазначено.