Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- /**
- 4. Adott egy nxm-es tábla, melynek minden mezője egy adott értékű kincset tartalmaz. A bal felső sarokból elindulva szeretnénk eljutni a jobb alsó sarokba úgy,
- hogy a lehető legtöbb kincset szedjük össze, tudva azt, hogy csak jobbra illetve le tudunk menni.
- Pl: n=4, m=4 és a bemeneti mátrix, amely a kincseket tartalmazza:
- 1 2 2 7 1 3 5 12
- 6 3 1 7 7 10 11 19
- 4 4 5 6 11 15 20 26
- 3 2 1 2 14 17 21 28
- */
- using namespace std;
- void visszakeres(int b[][50],int n, int m)
- {
- int o=1,s=1;
- cout<<s<<" "<<o<<endl;
- for(int i=1;i<=n+m-2;i++)
- {
- if(b[s+1][o]>b[s][o+1]){
- cout<<s+1<<" "<<o<<endl;
- s++;}
- else {cout<<s<<" "<<o+1<<endl;
- o++;}
- }
- }
- int main()
- {
- int a[50][50]= {0},b[50][50]= {0},n,m;
- cout<<"N ";
- cin>>n;
- cout<<"M ";
- cin>>m;
- for(int i=1; i<=n; i++)
- for(int j=1; j<=m; j++)
- cin>>a[i][j];
- for(int i=1; i<=n; i++)
- for(int j=1; j<=m; j++)
- {
- if(i==1 && j==1) b[i][j]=a[i][j];
- else if(i==1 && j!=1) b[i][j]=b[i][j-1]+a[i][j];
- else if(i!=1 && j==1) b[i][j]=b[i-1][j]+a[i][j];
- else if(b[i-1][j]>b[i][j-1])
- b[i][j]=b[i-1][j]+a[i][j];
- else b[i][j]=b[i][j-1]+a[i][j];
- }
- cout<<b[n][m];
- cout<<endl;
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++)
- cout<<b[i][j]<<" ";
- cout<<endl;}
- visszakeres(b,n,m);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement