Căutătorul de comori

Enunț:

O clădire este formată din camere dispuse într-un grid cu mxn elemente. Între două camere se poate trece doar dacă acestea sunt alăturate pe linie sau pe coloană. La ieșirea din camera (m; n) se află o comoară. Un căutător de comori intră în clădire prin camera (1; 1). Pentru fiecare cameră în care intră, i se cere să plătească o taxă (număr natural). Determinați suma minimă pe care trebuie să o plătească căutătorul de comori pentru a ajunge la comoara mult dorită.

Indicații de rezolvare:

Implementare:

Cod Sursa C++

// CautatorComoriCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
int a[100][100], s[100][100], m, n;
 
int min(int a, int b)
{
	if (a < b)
		return a;
	else
		return b;
}
 
void comoara()
{
	int i, j;
	s[0][0] = a[0][0];
	for (j = 1; j < n; j++)
		s[0][j] = s[0][j - 1] + a[0][j];
	for (i = 1; i < m; i++)
		s[i][0] = s[i - 1][0] + a[i][0];
	for (i = 1; i < m;i++)
	for (j = 1; j < n; j++)
		s[i][j] = min(s[i - 1][j], s[i][j - 1]) + a[i][j];
	cout << "Suma minima de plata: " << s[m - 1][n - 1] << endl;
}
 
int main()
{
	int i, j;
	cout << "m= ";
	cin >> m;
	cout << "n= ";
	cin >> n;
	for (i = 0; i < m;i++)
	for (j = 0; j < n; j++)
	{
		cout << "a[" << i << "][" << j << "]=";
		cin >> a[i][j];
	}
	comoara();
	system("pause");
}
 
 
 

Rezultat: