Manchester- 【矩阵】(太难了，如果你看了觉得匪夷所思，那多看几遍)

解题思路:
1.假设二维数组为  N=3

0   1   2    H=0  代表行：第一行 

3   4   5    H=1

6   7   8    H=2

H=3，没有这行，结束；

注意：以下程序使用了一维数组代替二维数组：(因为刚开始用全排列做的，一维数组直接把全排列搬过来就可，之后换方法就没改）

每一行的第一个元素，在一维数组中的下标为[H*N];

每行的最后一个元素，在一位数组中的下表为[H*N+N-1],即：[(H+1)*N-1]

 以下是递归关系：（得到所有不同矩阵）

（1）.到第三行（最后一行）右移N(N=3)次，每次得到一个新的矩阵，每得到一个矩阵，求其最大值；

（2）.到第二行移动三次，每移动一次，做一遍（1）；

（3）.到第一行移动三次，每移动一次，做一遍（2）；

  优化：

  因为

1   0   2     和  0   1   2

4   3   5           3   4   5

7   6   8           6   7   8      .....是一样的

所以第一行可以不用右移动；若不能理解的话，把所有的写出来，看看；

递归关系简化为：

（1）.到第三行（最后一行）右移N(N=3)次，每次得到一个新的矩阵，每得到一个矩阵，求其最大值；

（2）.到第二行移动三次，每移动一次，做一遍（1）；

注意，简化后，因为第一行没有排序，当输入N=1的时候，不能得出结果（具体看函数），所以当N==1时，结果单独输出；

if(N==1)//N==1直接输出结果，原因向下看
   printf("%d\n",A[0]);
          else         //否则进行排列递归，从第二行开始
          {
            pailie(A,N,1); //1表示从第二行开始移动（因为优化第一行不移动了），当N等于1时，看下面pailie
                               //实现，H==N，直接就返回了，所以N==1在上面单独输出
            free(A);
            printf("%d\n",comax_min);
          }

递归实现；

void pailie(int *A,int N,int H)
{

           if(H==N)     //当H==N，看上面例子，可以知道，前面已经到最后一行，所以返回上一个函数
             return;
            for(int j=0;j<N;j++)    //每一行移动N次
              {

                       pailie(A,N,H+1);   //递归到下一行

                      int t=A[N*(H+1)-1];     //记录这一行的最后一个元素
                       for(int i=N*(H+1)-1;i>N*H;i--)  //移动
                            A[i]=A[i-1];     
                              A[N*H]=t;

                        Colmax(A,N);   //求矩阵的最大值，同时里面会记录所有矩阵最大值的最小一个
              }
return ;
}

参考代码:

#include<stdio.h>
#include<malloc.h>
int comax_min;
void pailie(int *A,int N,int H);
void input(int *A,int N);
void Colmax(int *A,int N);
int main()
{
   int *A;
   int N;

   while(scanf("%d",&N)&&N!=-1)
   {
                 comax_min=100000;
                 A=(int *)malloc((N*N)*sizeof(int));
                 input(A,N*N);

                  if(N==1)
                     printf("%d\n",A[0]);
                   else
                       {
                           pailie(A,N,1);
                           free(A);
                           printf("%d\n",comax_min);
                       }

   }
return 0;
}

/*===================================================*/
void input(int *A,int N)
{
   for(int i=0;i<N;i++)
    scanf("%d",&A[i]);
}
/*===================================================*/
void pailie(int *A,int N,int H)
{

           if(H==N)
             return;
            for(int j=0;j<N;j++)
              {

                pailie(A,N,H+1);

                      int t=A[N*(H+1)-1];
                       for(int i=N*(H+1)-1;i>N*H;i--)
                            A[i]=A[i-1];
                              A[N*H]=t;

                        Colmax(A,N);

              }


return ;
}

/*===================================================*/
void Colmax(int *A,int N)   //求矩阵的最大值，并且求出所有矩阵中最大值最小的一个
{

   int max,sum=0;

   for(int j=0;j<N;j++)  //先求第一例的和
     sum+= A[j*N];
     max=sum;  //让最大值先等于第一列的和
     
   for(int i=1;i<N;i++)    //再求后面的列的和
   {   sum=0;
      for(int k=0;k<N;k++)
        {
          sum+=A[k*N+i];
        }
     if(max<sum)  //后面列的和更大，则更行max
     max=sum;

   }
  if(comax_min>max)   //记录所有矩阵最大值中最小的一个
    comax_min=max;
}

下面介绍全排列法以上方法就是它来的：（此方法仅供观赏，测试电脑性能）

同样把除了第一行以外的行，做全排列；

0   1   2    H=0  代表行：第一行 

3   4   5    H=1

6   7   8    H=2

把第二行做全排列，每得到一种排列，转向排列它的下一行，（同样每得到一种排列，排列它的下一行）；若是最后一行，排列这一行，每一种排列求出这个矩阵的最大值。

//整个实现过程就是全排列里面，加上递归全排列，和求矩阵最大值
void pailie(int *A,int index,int length,int H,int N)
{

   int j=0;

   if(index==length)  //得到一种排列
    {
        if(H==N-1)   //看是不是最后一行
           Colmax(A,N);   //是最后一行，求矩阵最大值
          
           else
             pailie(A,(H+1)*N,(H+2)*N,H+1,N);  //不是最后一行，递归下一行

    }
    else
     for(j = index;j < length; j++)
        {
            swap(&A[j],&A[index]);
            pailie(A,index+1,length,H,N);
            swap(&A[j],&A[index]);
        }
return ;
}

参考代码：

#include<stdio.h>
#include<malloc.h>
int comax_min=0;
void pailie(int *A,int index,int length,int H,int N);
void swap(int *x,int *y);
void input(int *A,int N);
void Colmax(int *A,int N);
int main()
{
   int *A;
   int N;
   while(scanf("%d",&N)&&N!=-1)
   {
         comax_min=100000;
        A=(int *)malloc((N*N)*sizeof(int));
        if(N==1)
         {
         input(A,N*N);
         printf("%d\n",A[0]);
         }
         else
           {
               input(A,N*N);
               pailie(A,1*N,N+N,1,N);
               printf("%d\n",comax_min);
           }
   }
return 0;
}

/*===================================================*/
void input(int *A,int N)
{
   for(int i=0;i<N;i++)
    scanf("%d",&A[i]);
}
/*===================================================*/
void pailie(int *A,int index,int length,int H,int N)
{

   int j=0;

   if(index==length)
    {
        if(H==N-1)
           Colmax(A,N);

           else
             pailie(A,(H+1)*N,(H+2)*N,H+1,N);

    }
    else
     for(j = index;j < length; j++)
        {
            swap(&A[j],&A[index]);
            pailie(A,index+1,length,H,N);
            swap(&A[j],&A[index]);
        }
return ;
}

/*===================================================*/
void Colmax(int *A,int N)
{

   int max,sum=0;

   for(int j=0;j<N;j++)
     sum+= A[j*N];
     max=sum;
   for(int i=1;i<N;i++)
   {   sum=0;
      for(int k=0;k<N;k++)
        {
          sum+=A[k*N+i];
        }
     if(max<sum)
     max=sum;
   }

  if(comax_min>max)
    comax_min=max;
}
/*===================================================*/
void swap(int *x,int *y)
{
  int z=(*x);
  (*x)=(*y);
  (*y)=z;
return ;
}

别忘点赞哦-.-