欢聚时代笔试题

#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;
}