Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stdlib.h>
- #include <vector>
- #include <climits>
- #include <string>
- using namespace std;
- void printVector(vector<vector<int>> arr){
- for (int i = 0; i < arr.size(); i++){
- for (int j = 0; j < arr[i].size(); j++){
- cout << arr[i][j] << " ";
- }
- cout << endl;
- }
- }
- int main(int argc, const char * argv[]) {
- int n, m, x = INT_MAX, y = INT_MAX;
- cin >> n >> m;
- vector<vector<int>> matrix(n); //едреный ввод
- for (int i = 0; i < n; i++){
- for (int j = 0; j < m; j++){
- string temp;
- cin >> temp;
- if (temp == "S"){
- x = i;
- y = j;
- matrix[i-x].push_back(0);
- }
- else if ((i >= x) && (j >= y)){
- matrix[i-x].push_back(stoi(temp));
- }
- }
- }
- for (int i = matrix.size() - 1; i > 0; i--){
- if (matrix[i].empty()){
- matrix.erase(matrix.begin() + i);
- }
- }
- //printVector(matrix);
- //cout << matrix.size() << " " << matrix[0].size() << endl;;
- vector<vector<int>> s_matrix (matrix.size(), vector<int>(matrix[0].size()));
- //printVector(s_matrix);
- for (int j = 1; j < matrix[0].size(); j++){
- s_matrix[0][j] = s_matrix[0][j-1] + matrix[0][j];
- }
- for (int i = 1; i < matrix.size(); i++){
- s_matrix[i][0] = s_matrix[i-1][0] + matrix[i][0];
- for (int j = 1; j < matrix[0].size(); j++){
- s_matrix[i][j] = max(matrix[i][j]+s_matrix[i-1][j], matrix[i][j]+s_matrix[i][j-1]);
- }
- }
- int coins = s_matrix[s_matrix.size() -1][s_matrix[0].size() - 1], i = s_matrix.size()-1, j = s_matrix[0].size()-1;
- vector<int> xi;
- vector<int> yj;
- xi.push_back(i);
- yj.push_back(j);
- cout << "Path:" << endl;
- while (i!=0|| j!=0){
- //cout << "(" << i+x << "," <<j+y <<") ";
- if (i == 0){
- j--;
- }
- else if (j == 0){
- i--;
- }
- else if (s_matrix[i-1][j] >= s_matrix[i][j-1]){
- i--;
- }
- else {
- j--;
- }
- xi.push_back(i);
- yj.push_back(j);
- }
- reverse(xi.begin(), xi.end());
- reverse(yj.begin(), yj.end());
- for (int i = 0; i < xi.size(); i++){
- cout << "(" << xi[i] + x << "," <<yj[i] + y <<") ";
- }
- cout << "\nCoins: " << coins;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement