//题目描述：牛牛和15个朋友玩打土豪分田地的游戏，牛牛决定让你来分田地，
//                    地主的土地可以看成是一个矩形，每个位置有一个价值。分割田地
//                    的方法是横竖各切3刀，分成16分，牛牛作为领导干部，总是选择总
//                    价值最小的一份田地，你作为牛牛最好的朋友，希望他分得的土地
//                    的价值和尽可能大，你知道这个值最大是多少吗？
//输入：每个输入包含一个测试用例，第一行包含两个整数n和m，表示矩阵的大小，
//            接下来n行每行包含m个0到9的数字，代表每块位置的价值
//输出：输出一行表示牛牛能分得田地的最大值
//题目来源：网易内推c++笔试第三道编程题

#include <iostream>
#include <vector>
#include <algorithm> 

using namespace std;

int compute_sum(const vector<vector<int> >& A,int a, int b, int c, int d)//左上角坐标(a,c)，右下角坐标(b,d)
{
    int sum = 0;
    for (int i =a ; i <= b; ++i)
    {
        for (int j = c; j <= d; ++j)
        {
            sum+=A[i][j];
        }
    }
    return sum;
}

int max_index(vector<int>& temp)//返回数组中最大元素对应的索引/下标
{
    int k = 0;
    int max = temp[0];
    for (int i = 1; i < temp.size(); ++i)
    {
        if (temp[i]>max)
        {
            max = temp[i];
            k = i;
        }
    }
    return k;
}

int get_min(vector<int>& temp)//返回数组中最小元素
{
    int min = temp[0];
    for (int i = 1; i < temp.size(); ++i)
    {
        if (temp[i]<min)
        {
            min = temp[i];
        }
    }
    return min;
}

int get_max(vector<int>& temp)//返回数组中最大元素
{
    int max = temp[0];
    for (int i = 1; i < temp.size(); ++i)
    {
        if (temp[i]>max)
        {
            max = temp[i];
        }
    }
    return max;
}

int X_cut(const vector<vector<int> >& A, vector<int>& X_num, const int& a)//水平方向下刀函数
{
    int min = 0;
    int max = 0;
    vector<int> temp;
    vector<int> sum;//记录每个块的总价值
    int top = 0;//记录子块的起始行号
    int tail = 0;//记录子块的末尾行号

    cout << "初始长度=" << X_num.size() << endl;

    if (X_num.size() == 0)
    {
        for (int pos = 0; pos <A.size() - 1; ++pos)//切口位置pos的取值范围是[0, A.size() - 2]
        {
            sum.push_back(compute_sum(A, 0, pos, 0, A[0].size() - 1));
            sum.push_back(compute_sum(A, pos + 1, A.size() - 1, 0, A[0].size() - 1));
            min = (sum[0] <= sum[1]) ? sum[0] : sum[1];

            cout << "min=" << min << endl;

            temp.push_back(min);
            sum.clear();
        }       
        X_num.push_back(max_index(temp));
        cout <<endl<<endl;
        if (X_num.size() == a)
        {
            int max_min = get_max(temp);
            return max_min;
        }
        temp.clear();
    }
        
     int flag = 0;
     while (X_num.size() != a)
     {
         for (int pos = 0; pos < A.size() - 1; ++pos)
         {
             flag = 0;
             for (int i = 0; i < X_num.size(); ++i)
             {
                 if (pos == X_num[i])
                 {                     
                     flag = 1;
                 }
             }
             if (flag == 1)  temp.push_back(0);//将旧位置标记为0,便于查找合适的切口
             if (flag == 0)//表示目标切口位置是新位置
             {
                 vector<int> temp2(X_num);
                 temp2.push_back(pos);
                 sort(temp2.begin(), temp2.end());

                 top = 0;
                 tail = temp2[0];
                 sum.push_back(compute_sum(A, top, tail, 0, A[0].size() - 1));
                 for (int i = 0; i < temp2.size() - 1; ++i)
                 {
                     top = temp2[i] + 1;
                     tail = temp2[i + 1];
                     sum.push_back(compute_sum(A, top, tail , 0, A[0].size() - 1));
                 }
                 top = temp2[temp2.size() - 1] + 1;
                 tail = A.size() - 1;
                 sum.push_back(compute_sum(A, top, tail, 0, A[0].size() - 1));

                 int min = get_min(sum);
                 temp.push_back(min);
                 cout << "min=" << min << endl;

                 temp2.clear();
                 sum.clear();
             }
         }
         X_num.push_back(max_index(temp));
         cout << endl<<endl;
         if (X_num.size() == a)
         {
             int max_min = get_max(temp);
             return max_min;
         }
         else
         {
             temp.clear();
         }
     }
}

 

int Y_cut(const vector<vector<int> >& A, const vector<int>& X_num,vector<int>& Y_num,int b)//竖直方向下刀函数
{
    int min = 0;
    int max = 0;
    vector<int> temp;
    vector<int> sum;//记录每个块的总价值
    int top = 0;//记录子块的起始列号
    int tail = 0;//记录子块的末尾列号

    cout << "初始长度=" << Y_num.size() << endl;
    vector<int> temp3(X_num);
    sort(temp3.begin(),temp3.end());

    if (Y_num.size() == 0)
    {
        for (int pos = 0; pos <A[0].size() - 1; ++pos)//切口位置pos的取值范围是[0, A[0].size() - 2]
        {
            top = 0;
            tail = temp3[0];
            sum.push_back(compute_sum(A, top, tail, 0, pos));
            sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1));

            for (int i = 0; i < temp3.size() - 1; ++i)
            {
                  top = temp3[i] + 1;
                  tail = temp3[i + 1];
                  sum.push_back(compute_sum(A, top, tail , 0, pos));
                  sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1));
            }

            top = temp3[temp3.size() - 1] + 1;
            tail = A.size() - 1;
            sum.push_back(compute_sum(A, top, tail, 0, pos));
            sum.push_back(compute_sum(A, top, tail, pos+1, A[0].size() - 1));
           
            min = get_min(sum);
            temp.push_back(min);
            cout << "min=" << min << endl;
            
            sum.clear();
        }       
        Y_num.push_back(max_index(temp));
        cout <<endl<<endl;
        if (Y_num.size() == b)
        {
            int max_min = get_max(temp);
            return max_min;
        }
        temp.clear();
    }

     int flag = 0;
     while (Y_num.size() != b)
     {
         for (int pos = 0; pos < A[0].size() - 1; ++pos)
         {
             flag = 0;
             for (int i = 0; i < Y_num.size(); ++i)
             {
                 if (pos == Y_num[i])
                 {                     
                     flag = 1;
                 }
             }
             if (flag == 1)  temp.push_back(0);//将旧位置标记为0,便于查找合适的切口
             if (flag == 0)//表示目标切口位置是新位置
             {
                 vector<int> temp4(Y_num);
                 temp4.push_back(pos);
                 sort(temp4.begin(), temp4.end());

                 sum.push_back(compute_sum(A, 0, temp3[0], 0,temp4[0] ));
                 for (int i = 0; i < temp3.size() - 1; ++i)
                 {
                     sum.push_back(compute_sum(A,temp3[i] + 1 ,temp3[i + 1] , 0,temp4[0] ));
                 }
                 sum.push_back(compute_sum(A,temp3[temp3.size() - 1] + 1 ,A.size() - 1 , 0, temp4[0]));

                 for (int j = 0; j < temp4.size() - 1; ++j)
                 {
                      top = temp4[j] + 1;
                      tail = temp4[j + 1];
                      sum.push_back(compute_sum(A, 0, temp3[0], top,tail ));
                      for (int i = 0; i < temp3.size() - 1; ++i)
                      { 
                           sum.push_back(compute_sum(A,temp3[i] + 1 ,temp3[i + 1] , top,tail ));
                      }
                      sum.push_back(compute_sum(A,temp3[temp3.size() - 1] + 1 ,A.size() - 1 , top, tail));
                 }

                 sum.push_back(compute_sum(A, 0, temp3[0],temp4[temp4.size() - 1] + 1 , A[0].size()-1));
                 for (int i = 0; i < temp3.size() - 1; ++i)
                 {
                     sum.push_back(compute_sum(A, temp3[i] + 1, temp3[i + 1], temp4[temp4.size() - 1] + 1, A[0].size()-1));
                 }
                 sum.push_back(compute_sum(A, temp3[temp3.size() - 1] + 1, A.size() - 1, temp4[temp4.size() - 1] + 1, A[0].size()-1));

                 min=get_min(sum);
                 temp.push_back(min);

                 cout << "min=" << min<< endl;

                 temp4.clear();
                 sum.clear();
             }
         }
         Y_num.push_back(max_index(temp));
         cout << endl<<endl;
         if (Y_num.size() == b)
         {
             int max_min = get_max(temp);
             return max_min;
         }
         else
         {
             temp.clear();
         }

     }
}


int main()
{
    int n = 0;
    cout << "请输入矩阵的行数n" << endl;
    cin >> n;  //矩阵行数
    int m = 0;
    cout << "请输入矩阵的列数m" << endl;
    cin >> m;  //矩阵列数
    int a = 0;
    cout << "请输入水平方向需要切的刀数a, a的范围[1,n)" << endl;  //a的范围[1,n)
    cin >> a;  //水平方向需要切的刀数
    int b = 0;
    cout << "请输入竖直方向需要切的刀数b, b的范围[1,m)" << endl;  //b的范围[1,m)
    cin >> b;  //竖直方向需要切的刀数

    vector<vector<int> > A(n); //二维数组来保存矩阵
    for (int i = 0; i < n; i++)
    {
        A[i].resize(m);
    }
    cout << "请以矩阵的形式输入矩阵" << endl;
    for (int i = 0; i < n; ++i)   //初始化二维数组
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> A[i][j];
        }
    }
    cout << "输入的二维数组为" << endl;
    for (int i = 0; i < n; ++i)   //初始化二维数组
    {
        for (int j = 0; j < m; ++j)
        {
            cout << "    " << A[i][j];
        }
        cout << endl;
    }
    vector<int> X_num;//存储水平方向下刀位置
    int value=X_cut(A, X_num, a);
    cout << endl << endl;
    cout << "下面依次输出水平方向下刀位置" << endl;
    for (int i = 0; i < X_num.size(); ++i)
    {
        cout <<"     "<< X_num[i];
    }
    cout << endl << endl << "value=" << value << endl << endl;

    vector<int> Y_num;//存储竖直方向下刀位置
    int value2 = Y_cut(A, X_num,Y_num, b);
    cout << endl << endl;
    cout << "下面依次输出竖直方向下刀位置" << endl;
    for (int i = 0; i < Y_num.size(); ++i)
    {
        cout << "     " << Y_num[i];
    }
    cout << endl << endl << "value2=" << value2 << endl << endl;

    cout << "最小的块可能取得的最大值为" << value2 << endl << endl;

    return 0;
}

笔试的时候题目没有看明白，回头想了想，在vs上写出来了，花了不少时间，编译运行成功。因为在VS2013上写的，有一些简单的cout说明语句没有删除，但是结果应该是正确的，程序还打印输出切割方法，感兴趣的大家可以看一下。