Fase Territoriale 2010
L’esercito di Orchi dell’Oscuro Signore degli Anelli marcia a ranghi serrati verso il Fosso di Helm.
Per contrastarne la marcia, Re Theoden decide di richiamare tutte le sue N armate per creare uno sbarramento unico, con le seguenti regole
- Campo di battaglia: è rappresentato da una tabella di dimensione N x N, le cui righe e colonne sono numerate da 1 a N.
- Posizione: ognuna delle N armate occupa una posizione distinta [i,j] nella tabella, all’incrocio tra la riga i e la colonna j.
- Movimento: permette di passare dalla posizione corrente [i,j] a una vicina con un giorno di marcia:
nord [i-1,j] (se i > 1),
sud [i+1,j] (se i < N),
est [i,j+1] (se j < N) e
ovest [i,j-1] (se j > 1).Una sola armata alla volta si sposta con un movimento.
- Sbarramento: si crea ponendo tutte le armate su un’unica riga R della tabella, attraverso una serie di movimenti.
Theoden vuole calcolare il numero minimo di movimenti necessari per spostare tutte le armate in un unico sbarramento sulla riga R.
Aiutate Theoden a calcolare tale numero minimo.Dati di input
Il file input.txt è composto da N+1 righe.
La prima riga contiene due interi positivi N e R, separati da uno spazio: il numero N di righe e di colonne nella tabella (nonché il numero di armate) e l’indice R della riga su cui far convergere lo sbarramento delle armate.
Ciascuna delle successive N righe contiene una coppia di interi i e j, separati da uno spazio, a indicare che un’armata è presente nella posizione [i,j] della tabella.Dati di output
Il file output.txt è composto da una sola riga contenente un intero non negativo, il minimo numero di movimenti per posizionare tutte le armate sulla riga R della tabella, in posizioni distinte all’interno di tale riga.
Assunzioni
- 2 <= N <= 500.
- Durante un movimento, due o più armate non possono mai occupare la stessa posizione intermedia.
Esempi
input.txt output.txt 1 8 3
5 5
1 6
2 2
6 5
3 2
7 1
1 2
8 131 2 8 5
5 7
5 2
5 3
5 6
5 1
5 8
5 5
5 40