Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- int main () {
- int n,m,minl=1000000000,x,ans;
- cin >> n >> m;
- vector <vector <int> > a(n,vector<int> (m));
- vector <vector <int> > cost(n,vector<int> (m));
- for (int i=0;i<n;i++)
- for (int j=0;j<m;j++)
- cin >> a[i][j];
- for (int i=0;i<n;i++)
- cost[i][m-1]=a[i][m-1];
- for (int i=n-2;i>0;i--)
- for (int j = 0; j < m; j++) {
- cost[i][j]=cost[i][j-1];
- if (j!=0)
- cost[i][j]=min(cost[i][j],cost[i-1][j-1]);
- if (j+1!=m)
- cost[i][j]=min(cost[i][j],cost[i-1][j+1]);
- if (i==0 && minl>cost[i][j]) {
- minl=cost[i][j];
- x=i;
- }
- }
- ans=minl;
- for (int i=1;i<n;i++) {
- cout << x+1 << " ";
- minl=cost[i][x];
- int b=x;
- if (x!=0 && minl>cost[i][x-1]) {
- minl=cost[i][x-1];
- b=x-1;
- }
- if (x!=m-1 && minl>cost[i][x+1]) {
- minl=cost[i][x+1];
- b=x+1;
- }
- x=b;
- }
- cout << x+1 << endl << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement