首页 > 代码库 > 【编程题目】对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一

【编程题目】对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一

45.雅虎(运算、矩阵):
1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)
某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。

 

这道题,是我目前为止做过的最最最最最麻烦、最繁琐的题目了。

 

思路:

把输入的矩阵一步步还原成 0 矩阵

一个数字,只可能伴随着它上下左右四个方向的数字变化。

①如果数字比它周围四个数的和要大,那么一定不满足条件。

②如果数字小于等于四周的数字和,且其四周仅有一个数字不为0: 不为0的那个周围数字的大小 -= 当前数字大小,将当前数字置零。  因为当前数字仅可能是那个不为0的数字引起的。

③如果数字等于四周的数字和,且其四周仅有多个个数字不为0:当前与四周的数字均置0。

④如果数字小于四周的数字和,且其四周仅有多个个数字不为0:无法判断,循环继续还原。

 

思路不难,但是对于矩阵的四个角、四条边和中间必须分开处理,让整个代码显得又臭又长!但实际上,跟一份代码被copy了9遍差不多。我还没有什么化简的方法。如果有人知道,希望可以告诉我。

/*45.雅虎(运算、矩阵):1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。*/#include <stdio.h>bool canBeCreatedbyZero(int ** M, int row, int col){    bool flag = false;    do     {        flag =false;        for (int i = 0; i < row; i++)         {            for (int j = 0; j < col; j++)            {                //打印每一次处理后的矩阵情况                printf("\n");                for (int r = 0; r < row; r++)                {                    for(int c = 0; c < col; c++)                    {                        printf("%d", *((int *)M + r * col + c));                    }                    printf("\n");                }                if ((i == 0) &&(j != 0 && j != col - 1)) //最上边                {                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if((r[j - 1] != 0 || r[j] != 0 || r[j + 1] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[3][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                        if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r[j - 1] + r[j + 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if((i == row - 1) &&(j != 0 && j != col - 1)) //最下边                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    if((r_1[j] != 0 || r[j - 1] != 0 || r[j] != 0 || r[j + 1] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                        if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        sum = r_1[j] + r[j - 1] + r[j + 1];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if ((j == 0) &&(i != 0 && i != row - 1)) //最左边                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if((r_1[j] != 0 || r[j] != 0 || r[j + 1] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r_1[j] + r[j + 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if ((j == col - 1) &&(i != 0 && i != row - 1))                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if((r_1[j] != 0 || r[j - 1] != 0 || r[j] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r_1[j] + r[j - 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if ( i == 0 && j == 0) //左上角                {                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if(( r[j] != 0 || r[j + 1] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                                            if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r[j + 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if (i == row - 1 && j == 0) //左下角                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    if((r_1[j] != 0|| r[j] != 0 || r[j + 1] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        sum = r_1[j] + r[j + 1];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if (i == 0 && j == col - 1) //右上角                {                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if((r[j - 1] != 0 || r[j] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r[j - 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if (i == row - 1 && j == col - 1) //右下角                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    if(r_1[j] != 0 || r[j - 1] != 0 || r[j] != 0) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                                                sum = r_1[j] + r[j - 1];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }                else if(i != 0 && i != row - 1 && j != 0 && j != col - 1) //非边界情况                {                    int * r_1 = (int *)M + (i - 1) * col;                    int * r = (int *)M + i * col;                    int * r1 = (int *)M + (i + 1) * col;                     if((r_1[j] != 0 || r[j - 1] != 0 || r[j] != 0 || r[j + 1] != 0 || r1[j] != 0)) //只在有非零元素的时候才做下面处理                    {                            flag = true;                        int has[4][2];                        int hasnum = 0; //该中心点上下左右有几个不为0的数字                        int sum = 0; //该中心点四周的数字相加的值                        if (r_1[j] != 0)                        {                            has[hasnum][0] = i - 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        if (r[j - 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j - 1;                            hasnum++;                        }                        if (r[j + 1] != 0)                        {                            has[hasnum][0] = i;                            has[hasnum][1] = j + 1;                            hasnum++;                        }                        if (r1[j] != 0)                        {                            has[hasnum][0] = i + 1;                            has[hasnum][1] = j;                            hasnum++;                        }                        sum = r_1[j] + r[j - 1] + r[j + 1] + r1[j];                        if (r[j] > sum) //数字大于周围的和 返回false                        {                            return false;                        }                        else if(hasnum == 1) //旁边只有一个不为0的 中心数字与旁边数字同步减少                        {                            int t = r[j];                            r[j] = 0;                            *((int *)M + has[0][0] * col + has[0][1]) -= t;                        }                        else if(r[j] == sum) //中心数字与旁边不为0的数字和相等                        {                            for(int ii = 0; ii < hasnum; ii++)                            {                                *((int *)M + has[ii][0] * col + has[ii][1]) = 0;                            }                            r[j] = 0;                        }                    }                }            }        }            }while(flag == true);    return true;}int main(){    int a[4][4] = {{0,1,0,0},                   {1,2,2,1},                   {0,1,3,0},                   {0,0,1,0}};     bool f = canBeCreatedbyZero((int **)a, 4, 4);     getchar();     return 0;}

 

网上找答案:居然没有找到别人写好的代码。都是说个思路就完了!!

有说用最大流可以搞定 http://blog.csdn.net/lihappy999/article/details/7395934

有说匈牙利算法的

http://www.cnblogs.com/GoAhead/archive/2012/06/01/2531144.html 给了个方法 但我没看懂

最让我无语的是翻答案就得到这样一段话:

A assignment problem. Two ways to solve. 1: duplicate each cell to as many as its value,
do Hungarian algorithm. Denote the sum of the matrix as M, the edge number is 2M, so
the complexity is 2*M*M; 2: standard maximum flow. If the size of matrix is NxN, then the
algorithm using Ford Fulkerson algorithm is M*N*N.
too complex... I will do this when I have time...