ture-impiedicate

Ture Impiedicate

Miruna învaţă şah. Ea a ajuns la piesa tură şi a înţeles că aceasta se poate deplasa doar pe orizontală sau pe verticală. De asemenea, ştie deja că dacă o altă piesă se află în calea unei ture aceasta poate fi atacată.
Miruna i s-a părut că este prea simplă teoria mutării unei ture şi şi-a imaginat următoarea problemă:

Pe o tablă de şah $N * N$ ea aşază la întâmplare $K$ ture. Nu poate pune $2$ ture în aceeaşi căsuţă (poziţie pe tablă). Ea doreşte să mute turele astfel încât, la finalul mutărilor, nicio tură să nu poată ataca altă tură şi, evident, să nu existe $2$ ture pe aceeaşi poziţie de pe tablă.

Pe o tablă de şah $N * N$ ea aşază la întâmplare $K$ ture. Ea doreşte să mute turele astfel încât, la finalul mutărilor, nicio tură să nu poată ataca altă tură.

După mai multe încercări fetiţa şi-a propus să determine numărul minim de mutări necesare pentru a obţine aşezarea finală a turelor.

Întrucât turele Mirunei sunt mai vechi şi cam împiedicate, ele se pot deplasa doar cu câte o căsuţă (la stânga, dreapta, în sus sau în jos) la fiecare mutare. O tură nu poate sări peste o altă tură, nu se poate muta pe o poziţie deja ocupată şi nici nu poate părăsi tabla de şah.

Întrucât turele Mirunei sunt mai vechi şi cam împiedicate, ele se pot deplasa doar cu câte o căsuţă (la stânga, dreapta, în sus sau în jos) la fiecare mutare. O tură nu poate sări peste o altă tură şi nici nu poate părăsi tabla de şah.

h2. Date de intrare

h2. Restricţii
* $K ≤ N$

* $1 ≤ c{~i~}, l{~i~} ≤ N$ oricare ar fi $i$ din ${1, 2, ... K}$

* $1 ≤ c{~i~}, l{~i~} ≤ N$ oricare ar fi $i$ din ${1, 2, ..., K}$
 
h2. Subtaskuri
 
table(subtask-uri). |_. Indice |_. Punctaj |_. Restricţii |
| $1$ | $15$ puncte | $N ≤ 9$ |
| $2$ | $15$ puncte | $N ≤ 100$ |
| $3$ | $20$ puncte | $N ≤ 2 000$ |
| $4$ | $50$ puncte | $N ≤ 100 000, K ≤ 2 000$ |

h2. Exemplu

| 5
|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="ture-impiedicate") ==