深度遍历 或者 优先级排序
#include<iostream>
#include<vector>
using namespace std;
struct MatrixElem
{
unsigned int n;
unsigned int x_ordinate;//将用于保存二维MatrixElem数组中本元素自身的下标
unsigned int y_ordinate;//将用于保存二维MatrixElem数组中本元素自身的下标
bool operator==(const MatrixElem& righthand)
//定义等号，新元素进入向量时用find函数检查是否已有横或纵坐标一样的元素
{
return x_ordinate==righthand.x_ordinate||y_ordinate==righthand.y_ordinate;
}
MatrixElem operator+(const MatrixElem& righthand)//定义加号，好算元素之和
{
MatrixElem result={n+righthand.n,0,0};//坐标不用管，用不着的
return result;
}
};
template<typename T>
class MyVector:public vector<T>
{
public:
bool find(T d)//定义一个在向量中查找指定元素的函数
{
iterator itr;
for(itr=begin();itr!=end();itr++)
if(*itr==d)return true;
return false;
};
T sum()
{
iterator itr;T t={0,0,0};
for(itr=begin();itr!=end();itr++)
t=t+*itr;
return t;
};
};
MatrixElem**me;
void Initialize(unsigned int n)
{
me=new MatrixElem*[n];
for(int i=0;i<n;i++)
me[i]=new MatrixElem[n];
}
void FreeElem(unsigned int n)
{
for(int i=0;i<n;i++)
delete []me[i];
delete me;me=0;
}
MyVector<MatrixElem> mv;
/*将用到的一些全局变量*/
int total=99999;
int result;
unsigned int N;//矩阵边长
void Scan(int y)
{
int i;MatrixElem tmp;
if(mv.size()!=N)
{
for(i=0;i<N;i++)
{
tmp=me[i][y];
if(!mv.find(tmp))
{
mv.push_back(tmp);
Scan(y+1);//扫下一行
mv.pop_back();
}
}
}
else
{
result=mv.sum().n;/*result, 全局变量, 保存相加结果*/
if(result<total) total=result;
return;
}
}
int main()
{
cout<<"请输入矩阵边长：";cin>>N;
Initialize(N);
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
{
me[i][j].n=(unsigned int)rand()%20;
me[i][j].x_ordinate=j; //把二维数组下标变成类的成员变量
me[i][j].y_ordinate=i; //把二维数组下标变成类的成员变量
}
for(i=0;i<N;i++)
{
for(int j=0;j<N;j++)
cout<<me[i][j].n<<'\t';
cout<<endl;
}
Scan(0);
cout<<"最小和："<<total<<endl;
return 0;
}
算到10花近半分钟
~~~
~~
~~~
程序代码：