阿里巴巴ios客户端4.8笔试第2题

现有一个二维数组，每个数组位置都有一个元素值，每一次可以朝上、下、左、右四个方向进行移动，最多可以移动不超过k的距离，每次移动到达的位置元素值一定要比当前位置的元素值要大，每次从左上角的位置开始移动，直至最终无法移动为止，求出从开始位置到最终停止位置所有经历过的元素值之和的最大值。

/****************************************************************以下是个人的解题答案************************************************************************/

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;

/**************将所有可能的元素之和放入res中*********************/
void get_max_sum(int **a,int k,vector<int> &res,vector<pair<int,int>> &tmp,int &sum,int x,int y,int n)
{
sum+=a[x][y];
//向上移动
for(auto i =1;i<=k;++i)
{
if(x==0)
break;
pair<int,int> up(make_pair(x-i,y));
if( (find(tmp.begin(),tmp.end(),up)==tmp.end())&&(up.first>=0&&up.first<n)&&(up.second>=0&&up.second<n)&&(a[up.first][up.second]>a[x][y]) )
{
tmp.push_back(up);
get_max_sum(a,k,res,tmp,sum,up.first,up.second,n);
}
}
//向下移动
for(auto i =1;i<=k;++i)
{
if(x==n-1)
break;
pair<int,int> down(make_pair(x+i,y));
if( (find(tmp.begin(),tmp.end(),down)==tmp.end())&&(down.first>=0&&down.first<n)&&(down.second>=0&&down.second<n)&&(a[down.first][down.second]>a[x][y]) )
{
tmp.push_back(down);
get_max_sum(a,k,res,tmp,sum,down.first,down.second,n);
}
}
//向左移动
for(auto i =1;i<=k;++i)
{
if(y==0)
break;
pair<int,int> left(make_pair(x,y-i));
if( (find(tmp.begin(),tmp.end(),left)==tmp.end())&&(left.first>=0&&left.first<n)&&(left.second>=0&&left.second<n)&&(a[left.first][left.second]>a[x][y]) )
{
tmp.push_back(left);
get_max_sum(a,k,res,tmp,sum,left.first,left.second,n);
}
}
//向右移动
for(auto i =1;i<=k;++i)
{
if(y==n-1)
break;
pair<int,int> right(make_pair(x,y+i));
if( (find(tmp.begin(),tmp.end(),right)==tmp.end())&&(right.first>=0&&right.first<n)&&(right.second>=0&&right.second<n)&&(a[right.first][right.second]>a[x][y]) )
{
tmp.push_back(right);
get_max_sum(a,k,res,tmp,sum,right.first,right.second,n);
}
}
res.push_back(sum);
sum-=a[x][y];
tmp.pop_back();
}

int main()
{
int num=0;
cin>>num;  //表示有几组测试用例
for(auto i =0;i<num;++i)
{
int n=0,k=0;
cin>>n>>k;
int a[n][n];
for(auto j=0;j<n;++j) //将输入的数据放入二维数组中
{
for(auto k =0;k<n;++k)
cin>>a[j][k];
}
vector<int> res;  //存放所有符合条件可能存在的元素值之和
vector<pair<int,int>> tmp; //存放从开始位置到结束位置所经历的路径
tmp.push_back(make_pair(0,0));
int sum=0;
get_max_sum(a,k,res,tmp,sum,0,0,n);  //将所有可能的元素之和放入res中
int max=0;
for(auto j =0;j<res.size();++j) //求出res中的最大值并输出！
max=max<res[j]?res[j]:max;
cout<<max<<endl;
}
return 0;
}