În Orașul Liniștit un număr de k tineri prieteni doresc să participe la un miting de protest. Deoarece cartierul în care locuiesc aceștia este mare, ei se vor deplasa spre punctul de întâlnire cu mașinile personale. Fiecare tânăr va aduce cu el o pancartă, pe care a desenat o singură literă din mulțimea A ... Z. Nu există două pancarte cu litere identice. Cele k litere formează un cuvânt, să-l notăm cuv, cunoscut.
Cartierul în care locuiesc tinerii poate fi codificat printr-o matrice cu n*m zone pătratice, dintre care unele sunt interzise. Se știe că o mașină consumă o unitate de combustibil la trecerea dintr-o zonă în zona vecină și nu consumă combustibil dacă staționează. Două zone sunt vecine dacă au în comun o latură. Pentru a face economie de combustibil, tinerii decid că dacă două mașini se întâlnesc într-o zonă și toate literele aflate în cele două mașini reprezintă o secvență din cuvântul cuv, atunci ei vor continua drumul cu o singură mașină, luând desigur toate pancartele cu ei. În caz contrar, mașinile își continuă drumul separat.
De exemplu, dacă cuvântul cuv este JOS, atunci mașina care transportă litera J poate prelua tânărul care aduce pancarta cu litera O, sau invers: mașina având litera O poate prelua tânărul care aduce litera J. Apoi se poate continua drumul spre mașina care transportă litera S. În altă variantă se pot reuni mai întâi literele S și O într-o singură mașină, dacă mașinile care le transportau se întâlnesc în aceeași zonă. Totuși, între mașina care transportă doar litera J și cea care transportă doar litera S nu se poate realiza un transfer, adică o reunire a literelor.
Cerința
Cunoscând dimensiunile cartierului n și m, cuvântul cuv, configurația cartierului și pozițiile inițiale ale tinerilor, se cere:
- Aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.
- Numărul minim de unități de combustibil consumați de către toate mașinile, știind că în final toți tinerii se vor reuni într-o singură mașină.
Date de intrare
Fișierul de intrare miting.in conține:
Pe prima linie, un număr natural p, care poate avea doar valoarea 1 sau 2.
Pe a doua linie două numere naturale n și m, separate printr-un spațiu.
Pe a treia linie, cuvântul cuv.
Pe următoarele n linii, câte m caractere pe linie reprezentând zonele cartierului. O zonă este interzisă dacă îi corespunde caracterul #, este liberă dacă îi corespunde caracterul _ (underline) și este punctul de plecare al unei mașini dacă îi corespunde una dintre literele cuvântului cuv.
Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai cerința 1.
În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural A, reprezentând aria minimă a unei submatrice a matricei care codifică cartierul, în care se situează toate pozițiile inițiale ale tinerilor.
Dacă valoarea lui p este 2, se va rezolva numai cerința 2.
În acest caz, în fişierul de ieşire miting.out se va scrie un singur număr natural C, reprezentând numărul minim de unități de combustibil consumate de către toate mașinile până la reunirea tinerilor, deci și a literelor, într-o singură mașină. În cazul în care nu există soluție, adică nu toți tinerii se pot reuni într-o singură mașină, se va scrie -1.
Restricții și precizări
2 ≤ n, m ≤ 602 ≤ k ≤ 10- Fie
znumărul zonelor interzise. Atunci0 ≤ z ≤ (n * m)/3 - În fiecare unitate de timp, o mașină poate să rămână pe loc în așteptarea alteia sau poate să treacă într-o zonă vecină, indiferent dacă zona respectivă este sau nu ocupată de o altă mașină.
- Lungimea laturii unei zone se consideră egală cu
1. - Pentru rezolvarea corectă a primei cerințe se acordă
20de puncte, iar pentru cerința a doua se acordă80de puncte. - Pentru
30%dintre testele cerinței2se garanteazăk ≤ 3.
Exemplul 1
miting.in
1 4 5 JOS #_O_# _#__S _#J_# ___#_
miting.out
9
Explicație
Submatricea de arie minimă care include toate literele are colțul stînga sus la linia 1 și coloana 3 și colțul dreapta jos la linia 3 și coloana 5. Aria este egală cu numărul de zone acoperite: 3 * 3 = 9.
Atenție! Pentru acest test se rezolvă doar cerința 1.
Exemplul 2
miting.in
2 5 7 BUN _#_#_#_ __N#__# _#__B__ U__#_#_ _#_#_#_
miting.out
6
Explicație
O variantă de consum minim este: U se deplasează cu două poziții la dreapta. Apoi B se deplasează cu două poziții la stânga. U se deplasează din nou cu o singură poziție în sus. În final, N coboară o poziție.
Remarcați că B s-a reunit cu U, apoi BU cu N.
Atenție! Pentru acest test se rezolvă doar cerința 2.
Exemplul 3
miting.in
2 6 7 ROST O#_#_#_ ___#__# _#_R___ ____#__ __#_S_# _#_T_#_
miting.out
9
Explicație
O variantă de consum minim este: O se deplasează cu o poziție în jos, apoi cu două poziții spre dreapta, coboară o poziție și în final se deplasează o poziție spre dreapta, unde se reunește cu R. Apoi S se deplasează cu o poziție la stânga. T urcă o poziție și se reunește cu 2. În final, mașina în care se găsesc S și T urcă două poziții și se întâlnește cu mașina în care se găsesc R și O. În această zonă, la linia 3 și coloana 4, toate literele se reunesc într-o singură mașină.
Atenție! Pentru acest test se rezolvă doar cerința 2.
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Miting:
/* prof. Constantin Galatan
Solutie O(nc^2 * n^3)
*/
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("miting.in");
ofstream fout("miting.out");
const int MaxN = 61, MaxC = 10, MaxV = 3601, Inf = 1 << 13,
di[] = { -1, 0, 1, 0}, dj[] = { 0, 1, 0, -1};
using Pair = pair<short, short>;
short c[MaxC][MaxC][MaxV];
int M, N, n, nc, cel[MaxN][MaxN]; // cel[i][j] = numarul de ordine corespunzator celulei (i, j)
string cuv;
deque<Pair> D;
queue<short> Q;
char H[MaxN][MaxN], ch;
inline void Lee(short i, short j);
bool Ok(short i, short j);
int main()
{
short imin = MaxN, jmin = MaxN, imax = -1, jmax = -1, p;
fin >> p >> N >> M >> cuv;
fin.get();
for (short i = 0; i < N; ++i)
{
fin.getline(H[i], 101);
for (short j = 0; j < M; ++j)
{
ch = H[i][j];
if ( isupper(ch) )
{
D.push_front({i, j});
imin = min(imin, i); jmin = min(jmin, j);
imax = max(imax, i); jmax = max(jmax, j);
}
else
if ( ch != '#')
D.push_back({i, j});
}
}
fin.close();
if ( p == 1 )
{
fout << (imax - imin + 1) * (jmax - jmin + 1) << '\n';
fout.close();
exit(0);
}
nc = cuv.size();
vector<int> pos('Z' + 1); // pozitiile caracterelor in cuvant
for ( int i = 0; i < nc; ++i)
pos[cuv[i]] = i;
// Dupa sortare primele nc celule vor contine literele i ordinea din cuvant
sort(D.begin(), D.begin() + nc, [&pos](const Pair& p1, const Pair& p2)
{ return pos[H[p1.first][p1.second]] < pos[H[p2.first][p2.second]]; }
);
n = D.size();
for (int k = 0, i, j; k < n; ++k)
{
i = D[k].first, j = D[k].second;
cel[i][j] = k;
}
for (int i = 0; i < nc; ++i)
{
for (int x = 0; x < n; ++x)
for (int j = 0; j < nc; ++j)
c[i][j][x] = Inf;
c[i][i][i] = 0;
Q.push(i);
Lee(i, i);
}
for ( int l = 2; l <= nc; ++l)
for (int i = 0; i < nc - l + 1; ++i)
{
int j = i + l - 1, cmin;
for (int x = 0; x < n; ++x)
{
cmin = c[i][j][x];
for (int k = i; k < j; ++k)
cmin = min(cmin, c[i][k][x] + c[k + 1][j][x]);
if ( cmin < c[i][j][x] )
c[i][j][x] = cmin,
Q.push(x);
}
if ( l < nc ) Lee(i, j);
}
short res = Inf;
for (short x = 0; x < n; ++x)
res = min(res, c[0][nc - 1][x]);
if ( res != Inf )
fout << res << '\n';
else
fout << -1 << '\n';
fout.close();
}
inline void Lee(short i, short j)
{
short I, J, iv, jv, x, y;
while ( !Q.empty() )
{
x = Q.front(); Q.pop();
I = D[x].first; J = D[x].second;
for (int dir = 0; dir < 4; ++dir )
{
iv = I + di[dir];
jv = J + dj[dir];
y = cel[iv][jv];
if ( Ok(iv, jv) && c[i][j][y] > c[i][j][x] + 1)
{
c[i][j][y] = c[i][j][x] + 1;
Q.push(y);
}
}
}
}
inline bool Ok(short i, short j)
{
if ( i < 0 || j < 0 || i >= N || j >= M ) return false;
if ( H[i][j] == '#') return false;
return true;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1621 Miting
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1621 Miting de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!