LeetCode题目:Minimum Path Sum,A*算法

By | 2012 年 10 月 16 日

Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.



用A*算法来做,以边作为中心来写代码就很快了。
代码超时,不过可以用双向查找以及最小值堆优化,相信优化之后能够满足时间要求。



代码:小集合0ms过,大集合超时,可以用双向dijkstra,以及最小值堆优化。

struct Point {
    int row;
    int col;
    int dist;
    bool rightVisited,downVisited;
    Point(int r,int c,int d = 0):row(r),col(c),dist(d),rightVisited(false),downVisited(false) {;}
    Point():row(0),col(0),dist(0),rightVisited(false),downVisited(false) {;}
    void print(){
        cout<<"r"<";
    }
};

class Solution {
public:
    int minPathSum(vector > &grid) {
        // Using Dijkstra algorithm
        const int veryLarge = 1000000;
        int rows = grid.size();
        if (rows == 0) return 0;
        int cols = grid[0].size();
        if (cols == 0) return 0;
        list starters;
        Point startPt(0,0,grid[0][0]);
        if(startPt.col == cols - 1 && startPt.row == rows - 1) return startPt.dist;
        //startPt.print();
        starters.push_back(startPt);
        while(starters.size()){
            list::iterator minStarterIt;
            bool rightMin;
            int minNextStep = veryLarge;
            for(list::iterator it = starters.begin(); it != starters.end(); ++ it) {
                Point &pt = *it;
                
                bool haveRight = pt.col + 1 < cols && !pt.rightVisited;
                int right = (haveRight ? grid[pt.row][pt.col + 1] + pt.dist : veryLarge);
                if(!haveRight) pt.rightVisited = true;
                
                bool haveDown = pt.row + 1 < rows && !pt.downVisited;
                int down = (haveDown ? grid[pt.row + 1][pt.col] + pt.dist : veryLarge);
                if(!haveDown) pt.downVisited = true;
                
                if (haveRight && right < minNextStep) {
                    minStarterIt = it;
                    minNextStep = right;
                    rightMin = true;
                }
                if (haveDown && down < minNextStep) {
                    minStarterIt = it;
                    minNextStep = down;
                    rightMin = false;
                }
            }
            Point &minPt = *minStarterIt;
            //minPt.print();
            Point nextStep(minPt.row,minPt.col);
            nextStep.rightVisited = false;
            nextStep.downVisited = false;
            nextStep.dist = minNextStep;
            if(rightMin) {
                nextStep.col += 1;
                minPt.rightVisited = true;
            } else {
                nextStep.row += 1;
                minPt.downVisited = true;
            }
            //nextStep.print();
            if (nextStep.row == rows - 1 && nextStep.col == cols - 1) {
                return nextStep.dist;
            } else {
                if(minPt.rightVisited && minPt.downVisited){
                    //remove from starters
                    starters.erase(minStarterIt);
                }
                starters.push_back(nextStep);
            }
        }
        return veryLarge;
    }
};



Code rewrite at 2013-2-5,60 ms pass large set.
Time complexity = O(rows * cols)
Space complexity = O(rows), Can optimized to min(rows,cols)

class Solution {
public:
    int minPathSum(vector > &grid) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int rows = grid.size();
        if(0 == rows) return 0;
        int cols = grid[0].size();
        if(0 == cols) return 0;
        //the min path sum at each colum
        int *pathsum = new int[rows];
        int *pathsumtemp = new int [rows];
        //initilazing the first colum
        for(int ir = 0; ir < rows; ++ir) {
            pathsum[ir] = grid[ir][0];
            if(ir>0) {
                pathsum[ir] += pathsum[ir-1];
            }
        }
        //calculate the rest of grid
        for(int ic = 1; ic < cols; ++ic) {
            //caculate the pathsum for colum ic into pathsumtemp
            pathsumtemp[0] = pathsum[0] + grid[0][ic];
            for(int ir = 1; ir < rows; ++ir) {
                int dist = pathsum[ir];//from left
                if(dist > pathsumtemp[ir-1])
                    dist = pathsumtemp[ir-1];//from top
                pathsumtemp[ir] = dist + grid[ir][ic];
            }
            //swap the pointer of pathsum and pathsumtemp
            int *temp = pathsum;
            pathsum = pathsumtemp;
            pathsumtemp = temp;
        }
        //return the last element in the pathsum
        int ret = pathsum[rows-1];
        delete pathsum;
        delete pathsumtemp;
        return ret;
    }
};

4 thoughts on “LeetCode题目:Minimum Path Sum,A*算法

  1. charles
    class Solution {
    public:
        int minPathSum(vector<vector>& grid) {
            for(int r=0;r<(int)grid.size();r++)
                for(int c=(0==r?1:0);c<(int)grid[r].size();c++)
                    0==r?grid[r][c]+=grid[r][c-1]:(0==c?grid[r][c]+=grid[r-1][c]:grid[r][c]+=min(grid[r-1][c],grid[r][c-1]));
            return grid[(int)grid.size()-1][(int)grid[0].size()-1];
        }
    };
    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注