We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #82: Path sum: three ways
  4. Discussions

Project Euler #82: Path sum: three ways

Contest ends in
Problem
Submissions
Leaderboard
Discussions

    You are viewing a single comment's thread. Return to all comments →

  • PatilKrishna
    3 years ago+ 1 comment

    This is my code it is not working on test case 5 and 6.

    #include <bits/stdc++.h>
    using namespace std;
    
    #define ll unsigned long long int
    #define MAX 1002
    
    struct Cell{
        int x, y;
        ll sum;
        Cell(){}
        Cell(int _x, int _y, ll _sum){
            x=_x, y=_y, sum=_sum;
        }
    };
    
    class compare{
        public:
            bool operator()(Cell a, Cell b){
                return a.sum > b.sum;
            }
    };
    
    ll pathsum(ll grid[MAX][MAX], int n){
    
        if (n==0)   return 0;
    
        int visited[MAX][MAX];
        memset(visited, 0, sizeof(visited));
    
        priority_queue<Cell, vector<Cell>, compare> que;
    
        for (int i=0; i<n; i++){
            que.push(Cell(i, 0, grid[i][0]));
            visited[i][0] = 1;
        }
    
        ll min_sum = INT_MAX;
    
        while (!que.empty()){
            
            Cell cell = que.top();
            que.pop();
    
            if (cell.y==n-1) {
                min_sum = min(min_sum, cell.sum);
                return min_sum;
            }
    
            //down
            if (cell.x+1>=0 && cell.x+1<n && cell.y>=0 && cell.y<n && visited[cell.x+1][cell.y]==0){
                visited[cell.x+1][cell.y]=1;
                que.push(Cell(cell.x+1, cell.y, cell.sum+grid[cell.x+1][cell.y]));  
            }
    
            //right
            if (cell.x>=0 && cell.x<n && cell.y+1>=0 && cell.y+1<n && visited[cell.x][cell.y+1]==0){
                visited[cell.x+1][cell.y]=1;
                que.push(Cell(cell.x, cell.y+1, cell.sum+grid[cell.x][cell.y+1]));  
            }
    
            //up
            if (cell.x-1>=0 && cell.x-1<n && cell.y>=0 && cell.y<n && visited[cell.x-1][cell.y]==0){
                visited[cell.x-1][cell.y]=1;
                que.push(Cell(cell.x-1, cell.y, cell.sum+grid[cell.x-1][cell.y]));  
            }
    
    
        }
    
        return (min_sum==INT_MAX)?-1:min_sum;
    }
    
    
    int main() {
    
        int n;        
        cin >> n;
        ll grid[MAX][MAX];
    
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++){
                cin >> grid[i][j];
            }
        }
    
        cout << pathsum(grid, n) << endl;
    
        return 0;
    }
    
    1|
    Permalink
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy