Question

Se consideră o clădire de formă dreptunghiulară formată din n*m camere, dispuse pe n linii și m coloane. Unele camere sunt închise, accesul în ele fiind imposibil. Intrarea în clădire este în camera de coordonate (1,1), iar ieșirea în camera de coordonate (n,m). Din orice cameră (i,j) se poate ajunge numai în camerele (i+1,j) sau (i,j+1), dacă aceasta nu este închisă.

Determinați în câte moduri se poate ajunge din camera (1,1) în camera(n,m). Deoarece numărul de posibilități poate fi foarte mare, se cere doar restul acestui număr la împărțirea cu 9901.

Date de intrare

Fişierul de intrare cladire1.in conţine pe prima linie numerele n m. Linia 2 conține k, numărul de camere închise. Următoarele k linii conțin câte 2 numere i j, reprezentând coordonatele (linie, coloană) camerelor închise.

Date de ieşire

Fişierul de ieşire cladire1.out va conţine pe prima linie numărul P, reprezentând în câte moduri se poate ajunge din camera (1,1) în camera (n,m), număr afișat modulo 9901.

Restricţii şi precizări1 ≤ n , m ≤ 10001 ≤ k ≤ 10001 ≤ i ≤ n, 1 ≤ j ≤ mcamera de intrare și cea de ieșire nu sunt închise
Exemplu

cladire1.in

3 3 2 1 2 3 1

cladire1.out

2

Answer 1

#include <iostream>
using namespace std;

int main(){
//elementele matricei a, a[i][j] 
//vor avea o valoare egala cu numarul de moduri in care
//poti ajunge de la i,j la n,m

int n,m,i,j,indice,k,a[100][100];
cout<<"Introduceti dimensiunile:";
cin>>n>>m;
cout<<"Introduceti numarul de usi inchise";
cin>>k;
//o initializam cu -1 pe toata ca sa aratam ca nu
//stim cate cai sunt deocamdata

for(i=0;i<n;i++){
for(j=0;j<m;j++){

a[i][j]=-1;
}
}
//usile aflate pe ultima coloana si ultima linie
//decat intr-un singur sens: in jos pentru coloana, si in dreapta pentru ultima linie
//deci toate aceste elemente vor avea valoarea 1
for(i=0;i<n;i++){
a[i][m-1]=1;
}
for(j=0;j<m;j++){
a[n-1][j]=1;
}
//citim usile inchise 
for(indice=0;indice<k;indice++){
cin>>i>>j;
//de la elementul i j nu se poate ajunge la n m pentru ca e inchisa
//deci ii dam valoarea 0
a[i-1][j-1]=0;
}
//de la fiecare usa poti ajunge la final folosindu-ne
//de suma modurilor la care poti ajunge de la usa din dreapta
//si de la usa de jos. Daca una dintre ele este blocata, atunci are valoarea 0
//deci reflecta intr-adevar ca nu exista moduri sa o iei pe acolo
for(i=n-2;i>=0;i--){
for(j=m-2;j>=0;j--){
//verificam actuala usa sa nu fie inchisa
if(a[i][j]!=0){
a[i][j]=a[i+1][j]+a[i][j+1];
}

}
}
//afisam toate posibilitatile din fiecare pozitie
for(i=0;i<n;i++){
for(j=0;j<m;j++){

cout<<a[i][j]<<" ";
}
cout<<endl;
}
//elementul 0,0 va arata exact cate moduri poti sa pornesti de la prima usa pana la ultima
//ignora faptul ca se numeste 0,0 in loc de 1,1 principiul e exact acelasi, numai ca va merge pana
//la usa n-1,n-1, distanta intre usi este tot de n-1
cout<<a[0][0]<<endl;
return 0;
}