Page 157 - MATINF Nr. 1

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 157

hart˘a se cunosc pozit , iile Scufit , ei s , i bunicii. Deplas˘arile sunt permise doar pe orizontal˘a s , i pe
vertical˘a.

Ajutat , i-o pe Scufit , ˘a s˘a ajung˘a pe traseul cel mai scurt de la locul ei la cel al bunicii, ocolind
obstacolele. Harta are latura de n p˘atr˘at , ele, avˆand aspectul unei matrice p˘atratice cu n linii
s , i n coloane. Liniile s , i respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei
corespund zonelor p˘atr˘at , elelor din foaia de caiet. O astfel de zon˘a poate fi colorat˘a cu ros , u sau

cu alb. Scufit , a trebuie s˘a treac˘a printr-un num˘ar minim de zone libere.

Cerint , ˘a
Scriet , i un program care s˘a determine num˘arul minim de zone libere pentru a alc˘atui traseul de
la Scufit , ˘a la bunic˘a.

Date de intrare
Fis , ierul de intrare scufita.in cont , ine pe prima linie dou˘a valori naturale n s , i m separate
printr-un spat , iu, reprezentˆand dimensiunea h˘art , ii, respectiv num˘arul de obstacole aflate pe hart˘a.
Fiecare dintre urm˘atoarele m linii cont , ine cˆate dou˘a numere naturale x s , i y separate printr-un
spat , iu, reprezentˆand pozit , iile obstacolelor de pe hart˘a (x reprezint˘a linia, iar y reprezint˘a
coloana zonei ˆın care se afl˘a obstacolul). Ultima linie a fis , ierului cont , ine patru numere naturale
x 1 , y 1 , x 2 , y 2 , separate prin cˆate un spat , iu, x 1 , y 1 reprezint˘a linia respectiv coloana pozit , iei
Scufit , ei, iar x 2 , y 2 reprezint˘a linia respectiv coloana pozit , iei bunicii.

Date de ies , ire
Fis , ierul de ies , ire scufita.out va cont , ine o singur˘a linie pe care va fi scris un num˘ar natural
care reprezint˘a num˘arul minim de zone prin care a trecut Scufit , a.

Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 175
• 1 ≤ m < n 2

• Traseul ˆıncepe cu zona unde se g˘ases , te Scufit , a s , i se termin˘a cu zona unde se g˘ases , te bunica
• Pentru datele de test exist˘a ˆıntotdeauna solut , ie

Exemplu
scufita.in scufita.out Explicat , ie
8 5 15 O modalitate de a constitui traseul este

2 3 parcurgerea primei linii, apoi a ultimei
3 6 coloane.
4 4
7 3
7 5
1 1 8 8

Timp maxim de execut , ie: 1 secund˘a/test.

Memorie total˘a disponibil˘a 5 MB.
Grat , iela Ghiordunescu, Pites , ti (Dan Barbilian, 2018)