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

hercule.out

Explicație

Cele două trasee posibile ale lui Hercule sunt:

şi

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 Hercule:

#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;
}

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 Adresa de email .

Rezolvarea problemei #937 Hercule

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #937 Hercule 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!

Rezolvare completă PbInfo #937 Hercule