Costruzione dei cancelli

Il Fattore Giovanni ha deciso di costruire una nuova recinzione attorno ad alcuni appezzamenti della sua fattoria, ma continua a distrarsi e finisce per costruire una recinzione dalla forma molto più stravagante di quanto avesse originariamente pianificato!

In particolare, il Fattore Giovanni inizia a muoversi dal punto $(0,0)$ e compie $n$ passi, spostandosi ogni volta di un'unità di distanza verso nord, sud, est o ovest. Ad ogni passo, traccia dietro di sé un segmento di recinzione di lunghezza unitaria. Ad esempio, se il suo primo passo è diretto verso nord, egli installa un segmento di recinzione da $(0,0)$ a $(0,1)$. Il Fattore Giovanni può tornare più volte negli stessi punti e persino tracciare più volte lo stesso segmento di recinzione. La sua recinzione può anche intersecare se stessa, se il suo percorso attraversa un tratto di recinzione già costruito.

Non sorprende che, una volta terminata la costruzione della recinzione, il Fattore Giovanni sia piuttosto insoddisfatto del risultato. In particolare, nota di aver potuto dividere alcuni appezzamenti della fattoria in regioni separate, in modo tale che ora sia impossibile spostarsi da una regione all'altra senza attraversare la recinzione. Il Fattore Giovanni vuole risolvere questo problema aggiungendo dei cancelli alla recinzione. Un cancello può essere installato su qualsiasi segmento unitario della recinzione da lui costruita, permettendo il passaggio tra i due lati di quel segmento.

Determinate il numero minimo di cancelli che il Fattore Giovanni deve installare affinché sia nuovamente possibile spostarsi da qualsiasi regione della fattoria a qualsiasi altra.