Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <climits>
- using namespace std;
- int b[1000][1000];
- int c[1000][1000];//costul optim pentru traseul care incepe de acolo
- int n;
- int m;
- ifstream fin("date.in");
- class Point{
- public:
- int x, y;
- Pointe(int x = 0, int y = 0) {}
- void setLocation(int x_, int y_)
- {
- x = x_;
- y = y_;
- }
- };
- void citire()
- {
- fin >> n;
- fin >> m;
- for (int i = 0; i < n; ++i)
- {
- for (int j = 0; j < m; ++j)
- fin >> b[i][j];
- }
- }
- int get(int l, int col)
- {
- if (l < 0 || l >= n)
- return INT_MIN;
- if (col < 0 || col >= m)
- return INT_MIN;
- return c[l][col];
- }
- int max(int a, int b)
- {
- return a > b ? a : b;
- }
- int main()
- {
- citire();
- for (int i = 0; i < n; ++i)
- c[i][m - 1] = b[i][m - 1];
- for (int col = m - 2; col >= 0; --col)
- {
- for (int lin = 0; lin < n; ++lin)
- {
- c[lin][col] = b[lin][col] + max(get(lin - 1, col + 1), get(lin + 1, col + 1));
- c[lin][col] = max(c[lin][col], b[lin][col] + get(lin, col + 1));
- }
- }
- // for(int i = 0; i < n; i++)
- // {
- // for(int j = 0; j < m; j++)
- // cout << c[i][j] << " ";
- // cout << endl;
- // }
- bool unic = true;
- int maxVal = -1;
- Point p;
- for (int l = 0; l < n; ++l)
- {
- if (c[l][0] > maxVal)
- {
- maxVal = c[l][0];
- p.x = l;
- }
- else
- if (c[l][0] == maxVal)
- unic = false;
- }
- cout << maxVal << endl;
- cout << p.x + 1 << " " << p.y + 1<< endl;
- for (int col = 0; col < m - 1; ++col)
- {
- int ne = get(p.x - 1, col + 1);
- int e = get(p.x, col + 1);
- int se = get(p.x + 1, col + 1);
- if (ne == e || ne == se || e == se)
- {
- unic = false;
- }
- if (ne > e)
- {
- p.setLocation(p.x - 1, col + 1);
- }
- else if (e > se)
- {
- p.setLocation(p.x, col + 1);
- }
- else
- {
- p.setLocation(p.x + 1, col + 1);
- }
- cout << p.x + 1 << " " << p.y + 1 << endl;
- }
- if (unic)
- {
- cout << "traseu unic";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement