宽度优先搜索,之前TLE是因为写成了深度优先搜索。
后来一次AC附上代码:
class Solution { public: int rows; int cols; int minnow; int minPathSum(vector<vector<int> > &grid) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. rows = grid.size()-1; cols = grid[0].size()-1;</p> <pre><code> vector&lt;vector&lt;int&gt;&gt; copygrid(grid.size()); int sum = 0; for(int i = 0;i &lt; grid.size();i++) { for(int j = 0;j &lt; grid[0].size();j++) { sum += grid[i][j]; } } for(int i = 0;i &lt; grid.size();i++) { vector&lt;int&gt; tmp(grid[0].size()); for(int j = 0;j &lt; grid[0].size();j++) { tmp[j] = sum; } copygrid[i] = tmp; } copygrid[0][0] = grid[0][0]; int px[10000],py[10000]; int cpx[20000],cpy[20000]; int index = 0; px[index] = 0; py[index++] = 0; while(true) { int top = index; index = 0; for(int i = 0;i &lt; top;i++) { int x = px[i]; int y = py[i]; if(x + 1 &lt;= rows) { if(copygrid[x][y] + grid[x+1][y] &lt; copygrid[x+1][y]) { copygrid[x+1][y] = copygrid[x][y] + grid[x+1][y]; cpx[index] = x+1; cpy[index] = y; index++; } } if(y + 1 &lt;= cols) { if(copygrid[x][y] + grid[x][y+1] &lt; copygrid[x][y+1]) { copygrid[x][y+1] = copygrid[x][y] + grid[x][y+1]; cpx[index] = x; cpy[index] = y+1; index++; } } } if(index == 0) break; for(int i = 0;i &lt; index;i++) { px[i] = cpx[i]; py[i] = cpy[i]; } } return copygrid[rows][cols]; } </code></pre> <p>};