欢聚时代笔试题
1.输入一个矩阵，从左上角走到右下角：向右、向下可以走， 向下优先，找出最短路径，需要输出走过的位置
#欢聚集团##笔试题目#
我用backtracking加剪枝只能通过40%，可能用动态规划更好，但不知道动态规划怎么保存路径，有大神做出来了吗，求教
#include <iostream>
#include <vector>
#include <algorithm>
vector<vector<int>> shared;
void backtracking(vector<vector<int>> &board,vector<vector<int>> &prune, int x, int y, int n, int m, int sum, int &res, vector<vector<int>> tra){
if(x<0||x>=m || y<0||y>=m)
return ;
if(sum>=res) return ;
if(x==n-1 && y==m-1){
if(sum<res){
res=sum;
shared=tra;
}
}
sum+=board[x][y];
if(sum>prune[x][y]) return;
else prune[x][y]=sum;
tra.push_back({x,y});
backtracking(board,prune,x+1,y,n,m,sum,res,tra);
backtracking(board,prune,x,y+1,n,m,sum,res,tra);
}
int main(){
int m,n;
cin>>n>>m;
vector<vector<int>> prune(n,vector<int>(m,INT_MAX));
vector<vector<int>> board(n,vector<int>(m,0));
for(int i=0;i<n; i++)
for(int j=0;j<m;j++)
cin>>board[i][j];
int res=INT_MAX;
vector<vector<int>> start;
backtracking(board,prune,0,0,n,m,0,res,start);
for(vector<vector<int>>::const_iterator vit=shared.begin();vit!=shared.end();vit++){
vector<int> tmp=*vit;
cout<<tmp[0]<<" "<<tmp[1]<<endl;
}
cout<<n-1<<" "<<m-1<<endl;
return 0;
} 
投递美团等公司10个岗位