博客

题目描述：

牛牛和 15 个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），表示田地的大小，接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。

输出描述:

输出一行表示牛牛所能取得的最大的价值。

输入例子:

4 4

3332

3233

3332

2323

输出例子:

2

算法思路

我已开始想不出来很好的思路，然后瞄了一眼其他人的解答，看了一个找出最小的，然后合并行和列，直到最终结果是4行4列的思路，虽然我感觉这贪心不正确，然而我想到的穷举法时间复杂度太高，就把这个思路实现了一下，一如神坑似海，花费了我2小时40分钟debug+调试+运行+提交代码，结果还不是太。。。。

代码如下：

// FenTianDi.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;


struct Pos
{
    int i, j;
    Pos() :i(0), j(0) {}
    Pos(int a, int b) :i(a), j(b) {}
};

void print(int ** arr, int n, int m)
{
    cout << "\n***********************************\n";
    for (int i = 0;i < n;++i)
    {
        cout << endl;
        for (int j = 0;j < m;++j)
            cout << arr[i][j] << " ";
    }
    cout << "\n";
}

Pos arrMinPos(int ** arr, int n, int m)
{
    int min = arr[0][0];
    Pos minPos(0, 0);
    for (int i = 0;i < n;++i)
        for (int j = 0;j < m;++j)
        {
            if (arr[i][j] < min)
            {
                min = arr[i][j];
                minPos = Pos(i, j);
            }
        }
    return minPos;
}



int ** newarr(int n, int m)
{
    int ** arr = new int*[n];
    for (int i = 0;i < n;++i)arr[i] = new int[m];
    return arr;
}

void delarr(int ** arr, int n, int m)
{
    for (int i = 0;i < n;++i) 
    {
        delete arr[i]; 
        arr[i] = nullptr;
    }
    delete arr;
    arr = nullptr;
}


int main()
{
    ifstream fin("file01.txt");
    int m, n;
    fin >> n >> m;// n 行，每行包含 m 个
    int ** arr = new int*[n];
    char tmp;
    for (int i = 0;i < n;++i)arr[i] = new int[m];
    for (int i = 0;i < n;++i)
        for (int j = 0;j < m;++j)
        {
            fin >> tmp;
            arr[i][j] = tmp - '0';
        }


    if (n == 4 && m == 4)
    {
        Pos pmin = arrMinPos(arr, n, m);
        cout << arr[pmin.i][pmin.j] << endl;
        return 0;
    }
    else if (n <= 3 || m <= 3)cout << "\nError input !!!\n";

    int tn = n, tm = m;
    while (!(tn == 4 && tm == 4))
    {
        Pos pmin = arrMinPos(arr, tn, tm);
        int valmin = arr[pmin.i][pmin.j];
        int choose = -1;
        int ** narrUP = nullptr, ** narrDOWN = nullptr, ** narrLEFT = nullptr, ** narrRIGHT = nullptr;
        bool flag1 = false, flag2 = false, flag3 = false, flag4 = false;
        if (tn > 4)//和上下行合并;
        {
            if (pmin.i > 0)//和上一行合并,判断是不是第一行;
            {
                narrUP = newarr(tn - 1, tm);
                flag1 = true;

                for (int i = 0;i <= pmin.i - 2;++i)
                    for (int j = 0;j <= tm - 1;++j)
                        narrUP[i][j] = arr[i][j];

                for (int j = 0;j <= tm - 1;++j)
                    narrUP[pmin.i - 1][j] = arr[pmin.i - 1][j] + arr[pmin.i][j];

                for (int i = pmin.i;i <= tn - 2;++i)
                    for (int j = 0;j <= tm - 1;++j)
                        narrUP[i][j] = arr[i + 1][j];
            }
            if (pmin.i < tn - 1)//和下一行合并,判断是不是最后一行;
            {
                narrDOWN = newarr(tn - 1, tm);
                flag2 = true;

                for (int i = 0;i <= pmin.i - 1;++i)
                    for (int j = 0;j <= tm - 1;++j)
                        narrDOWN[i][j] = arr[i][j];

                for (int j = 0;j <= tm - 1;++j)
                    narrDOWN[pmin.i][j] = arr[pmin.i + 1][j] + arr[pmin.i][j];

                for (int i = pmin.i + 1;i <= tn - 2;++i)
                    for (int j = 0;j <= tm - 1;++j)
                        narrDOWN[i][j] = arr[i + 1][j];
            }
        }

        if (tm > 4)//和左右列合并;
        {
            if (pmin.j > 0)//和第一列合并,判断是不是第一;
            {
                narrLEFT = newarr(tn, tm - 1);
                flag3 = true;

                for (int i = 0;i <= tn - 1;++i)
                    for (int j = 0;j <= pmin.j - 2;++j)
                        narrLEFT[i][j] = arr[i][j];

                for (int i = 0;i <= tn - 1;++i)
                    narrLEFT[i][pmin.j - 1] = arr[i][pmin.j - 1] + arr[i][pmin.j];

                for (int i = 0;i <= tn - 1;++i)
                    for (int j = pmin.j;j <= tm - 2;++j)
                        narrLEFT[i][j] = arr[i][j + 1];
            }
            if (pmin.j < tm - 1)//和下一行合并,判断是不是最后一行;
            {
                narrRIGHT = newarr(tn, tm - 1);
                flag4 = true;

                for (int i = 0;i <= tn - 1;++i)
                    for (int j = 0;j <= pmin.j - 1;++j)
                        narrRIGHT[i][j] = arr[i][j];

                for (int i = 0;i <= tn - 1;++i)
                    narrRIGHT[i][pmin.j] = arr[i][pmin.j] + arr[i][pmin.j + 1];

                for (int i = 0;i <= tn - 1;++i)
                    for (int j = pmin.j + 1;j <= tm - 2;++j)
                        narrRIGHT[i][j] = arr[i][j + 1];
            }
        }

        int min1 = 800000, min2 = 800000, min3 = 800000, min4 = 800000;

        print(arr, tn, tm);//测试代码;

        if (flag1)
        {
            print(narrUP, tn - 1, tm);//测试代码;
            Pos p = arrMinPos(narrUP, tn - 1, tm);
            min1 = narrUP[p.i][p.j];
            if (valmin <= min1)choose = 1;
        }
        if (flag2)
        {
            print(narrDOWN, tn - 1, tm);
            Pos p = arrMinPos(narrDOWN, tn - 1, tm);
            min2 = narrDOWN[p.i][p.j];
            if (valmin <= min2)choose = 2;
        }
        if (flag3)
        {
            print(narrLEFT, tn, tm - 1);
            Pos p = arrMinPos(narrLEFT, tn, tm - 1);
            min3 = narrLEFT[p.i][p.j];
            if (valmin <= min3)choose = 3;
        }
        if (flag4)
        {
            print(narrRIGHT, tn, tm - 1);
            Pos p = arrMinPos(narrRIGHT, tn, tm - 1);
            min4 = narrRIGHT[p.i][p.j];
            if (valmin <= min4)choose = 4;
        }
        switch (choose)
        {
        case 1:
            delarr(arr, tn, tm);
            if(flag2)delarr(narrDOWN, tn - 1, tm);
            if (flag3)delarr(narrLEFT, tn, tm - 1);
            if (flag4)delarr(narrRIGHT, tn, tm - 1);
            arr = narrUP;
            --tn;
            break;
        case 2:
            delarr(arr, tn, tm);
            if (flag1)delarr(narrUP, tn - 1, tm);
            if (flag3)delarr(narrLEFT, tn, tm - 1);
            if (flag4)delarr(narrRIGHT, tn, tm - 1);
            arr = narrDOWN;
            --tn;
            break;

        case 3:
            delarr(arr, tn, tm);
            if (flag1)delarr(narrUP, tn - 1, tm);
            if (flag2)delarr(narrDOWN, tn - 1, tm);
            if (flag4)delarr(narrRIGHT, tn, tm - 1);
            arr = narrLEFT;
            --tm;
            break;
        case 4:
            delarr(arr, tn, tm);
            if (flag1)delarr(narrUP, tn - 1, tm);
            if (flag2)delarr(narrDOWN, tn - 1, tm);
            if (flag3)delarr(narrLEFT, tn, tm - 1);
            arr = narrRIGHT;
            --tm;
            break;
        }

    }
    Pos pmin = arrMinPos(arr, 4, 4);
    cout << arr[pmin.i][pmin.j] << endl;

    /*for (int i = 0;i < n;++i)
    {
        cout << endl;
        for (int j = 0;j < m;++j)
            cout << arr[i][j] << " ";
    }*/



    fin.close();
    return 0;
}