Este anul 2019, dar Zmeul-Cel-Rău și Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a n linii și m coloane. Vom numerota liniile de la 1 la n, iar coloanele de la 1 la m, astfel că fiecare cameră poate fi identificată prin numărul liniei și al coloanei pe care se află.
Orice cameră are patru pereți și câte o ușă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia i și coloana j poate comunica cu camerele (i-1,j), (i,j+1), (i+1,j), (i,j-1) (desigur, dacă acestea există). Fiecare cameră are asociat un cod. Ușile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subșir al cuvântului memorat pe cartela magnetică, atunci ușile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reușit să-i trimită lui Făt-Frumos o cartelă magnetică.
Cerința
Scrieți un program care rezolvă următoarele două cerințe:
Este anul 2019, dar Zmeul-Cel-Rău și Făt-Frumos luptă în continuare. Zmeul l-a prins pe Făt-Frumos şi l-a închis în una dintre camerele bârlogului său. Un bârlog de zmeu are forma unui tablou bidimensional, în care camerele sunt plasate sub forma a n linii și m coloane. Vom numerota liniile de la 1 la n, iar coloanele de la 1 la m, astfel că fiecare cameră poate fi identificată prin numărul liniei și al coloanei pe care se află.
Orice cameră are patru pereți și câte o ușă pe fiecare perete prin care poate comunica cu camerele învecinate. Mai exact, camera de pe linia i și coloana j poate comunica cu camerele (i-1,j), (i,j+1), (i+1,j), (i,j-1) (desigur, dacă acestea există). Fiecare cameră are asociat un cod. Ușile din orice cameră se pot deschide cu o cartelă magnetică. Dacă codul camerei este un subșir al cuvântului memorat pe cartela magnetică, atunci ușile din camera respectivă se vor deschide folosind cartela. Ileana Cosânzeana a reușit să-i trimită lui Făt-Frumos o cartelă magnetică.
Cerința
Scrieți un program care rezolvă următoarele două cerințe:
1. determină numărul de camere în care ar putea ajunge Făt-Frumos folosind cartela primită de la Ileana Cosânzeana;
2. determină numărul minim de camere prin care trece Făt-Frumos pentru a ieși din bârlogul zmeului (adică poate deschide ușa unei camere prin care ajunge în exteriorul bârlogului).
Date de intrare
Fișierul de intrare barlog.in conține pe prima linie cerința c care trebuie să fie rezolvată (1 sau 2). Pe a doua linie se află două numere naturale n m, reprezentând numărul de linii și respectiv numărul de coloane ale tabloului care reprezintă bârlogul zmeului. Pe următoarele n linii se află câte m cuvinte, reprezentând în ordine codurile de acces ale camerelor din bârlogul zmeului. Pe ultima linie sunt două numere naturale și un cuvânt lin col cuv, reprezentând linia și coloana camerei în care a fost închis Făt-Frumos, precum și cuvântul înscris pe cartela magnetică primită de Făt-Frumos de la Ileana Cosânzeana. Valorile scrise pe aceeași linie sunt separate prin câte-un spațiu.
Date de ieșire
Fișierul de ieșire barlog.out va conține o singură linie pe care va fi scris un număr natural determinat conform cerinței c.
Restricții și precizări
2 ≤ n, m ≤ 100- Codurile camerelor și cuvântul de pe cartelă sunt cuvinte nevide, formate din maximum
20de litere mici ale alfabetului englez. - Pentru datele de test, Făt-Frumos va putea ieși întotdeauna din bârlogul zmeului.
- Cuvântul
aeste un subșir al cuvântuluibdacă literele dinase găsesc înbîn aceeași ordine. De exempluarmaeste un subșir al cuvântuluimarama, dar nu și al cuvântuluitamara. - Pentru teste valorând
40%din punctaj cerința este1. - În concurs s-au acordat
10puncte din oficiu. Aici se acordă pentru testele din exemple.
Exemplul 1:
barlog.in
1 5 4 ana are mere bune dana cere pere multe cra ana vrea pere dar dan nu are sunt bune pe care 3 2 caravana
barlog.out
7
Exemplul 2:
barlog.in
2 5 4 ana are mere bune dana cere pere multe cra ana vrea pere dar dan nu are sunt bune pe care 3 2 caravana
barlog.out
2
Explicație
Camerele în care poate intra Făt-Frumos sunt: (3,2), (3,3), (2,2), (3,1), (4,2), (2,1), (4,1). Poate ieși din bârlog prin camera (3,1).
#include <bits/stdc++.h>
using namespace std;
ifstream cin("barlog.in");
ofstream cout("barlog.out");
#define MaxN 101
#define Smax 21
#define Inf 0x3f3f3f
int cer, n, m, Xf, Yf;
bool ok[MaxN][MaxN];
char mat[MaxN][MaxN][Smax];
int dist[MaxN][MaxN] = {Inf} , nr;
struct poz
{
int i , j;
};
const int di[] = {0, 0, 1, -1};
const int dj[] = {1, -1, 0, 0};
queue <poz>Q;
int inside(int i , int j)
{
return i >= 1 && i <= n && j >= 1 && j <= m;
}
void lee(int i , int j)
{
poz x;
x.i = i;
x.j = j;
Q.push(x);
nr++;
dist[i][j] = 1;
while(!Q.empty())
{
x = Q.front();
for(int i = 0 ; i < 4 ; i++)
{
int inou = x.i + di[i];
int jnou = x.j + dj[i];
if(inside(inou , jnou) && ok[x.i][x.j] == 1 && dist[inou][jnou] == 0)
{
poz y;
y.i = inou;
y.j = jnou;
Q.push(y);
dist[inou][jnou] = dist[x.i][x.j] + 1;
nr++;
}
}
Q.pop();
}
}
bool searchs(char a[], char b[])
{
int i = 0, n = strlen(a);
int indb = 0, lb = strlen(b);
while (i < n)
{
if (a[i] == b[indb])i ++, indb ++;
else i ++;
if (indb == lb)return 1;
}
return 0;
}
int main()
{
char cheie[Smax];
cin >> cer >> n >> m;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
cin >> mat[i][j];
cin >> Xf >> Yf;
cin >> cheie;
int nr1 = 0;
for (int i = 1; i <= n; ++ i)
for (int j = 1; j <= m; ++ j)
{
if (searchs(cheie, mat[i][j]))
{
ok[i][j] = 1;
}
}
lee(Xf, Yf);
int dmin = Inf;
for(int i = 1; i <= n; ++ i)
{
if(dist[i][1] != 0 && ok[i][1] == 1)
dmin = min(dmin, dist[i][1]);
if(dist[i][m] != 0 && ok[i][m] == 1)
dmin = min(dmin, dist[i][m]);
}
for (int i = 1; i <= m; ++ i)
{
if(dist[1][i] != 0 && ok[1][i] == 1)
dmin = min(dmin, dist[1][i]);
if(dist[n][i] != 0 && ok[n][i] == 1)
dmin = min(dmin, dist[n][i]);
}
if(cer == 2)cout << dmin;
else cout << nr;
return 0;
}
