# PBinfo #937 – Hercule – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Hercule trebuie sa strabată un labirint cu capcane reprezentat de o matrice cu n linii și m coloane. Pentru fiecare celula a labirintului, se cunoaște timpul exprimat în minute după care celula respectivă devine capcană. După ce o celula devine capcana, Hercule piere dacă intră în acea celulă. Initial Hercule se află în celula de coordonate (1, 1) și trebuie să ajungă în celula de cordonate (n,m).

Sa se afișeze numarul total de drumuri pe care le poate urma Hercule prin labirint, astfel încât Hercule să nu piară.

Date de intrare
Fișierul de intrare hercule.in conține pe prima linie numerele n m, iar pe următoarele n linii câte m valori naturale.

Date de ieșire
Fișierul de ieșire hercule.out va conține pe prima linie numărul total de drumuri prin care Hercule poate ajunge în celula destinație.

Restricții și precizări

1 ≤ n , m ≤ 10
Hercule nu poate intra de mai multe ori in aceeasi celula
Hercule are nevoie de un minut,ca sa treacă dintr-o celula într-una vecină
Hercule se deplasează pe direcțiile N-S și E-V.

Exemplu:
hercule.in

4 5
4 1 1 8 1 
6 3 4 5 1 
3 2 8 8 8 
1 3 4 2 9 
hercule.out

2
Explicație
Cele două trasee posibile ale lui Hercule sunt:

1 0 0 0 0 
2 3 4 5 0 
0 0 0 6 7 
0 0 0 0 8 
şi

1 0 0 0 0 
2 3 4 0 0 
0 0 5 6 7 
0 0 0 0 8

## Cod sursă C++

```cpp
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("hercule.in");
ofstream fout("hercule.out");
int n, m, a[25][25], b[25][25], nrsol = 0;
const int di[]={0,0,1,-1}, dj[]={1,-1,0,0};
void afis(){
	nrsol++;
	return;
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j <= m ; ++j)
			cout << b[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}
void back(int i, int j, int pas)
{
	if(i >= 1 && i <= n && j >= 1 && j <= m && pas <= a[i][j] && b[i][j] == 0)
	{
		b[i][j] = pas;
		if(i == n && j == m)
			nrsol++;
		else
			for(int k = 0 ; k < 4 ; ++k)
				back(i + di[k], j + dj[k], pas + 1);
		b[i][j] = 0;
	}
}
int main()
{
	fin >> n >> m;
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
			fin >> a[i][j];
	back(1, 1, 1);
	fout << nrsol;
	//cout << nrsol;
	return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/937)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/937/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-937/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)