【100题】第四十五题 雅虎面试两道题（矩阵判断、数组划分）

一，对于一个整数对于一个整数矩阵矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

分析：对任意一个位置,他的值不大于周围(上下左右)4个临格的数值的和，如果大于则该矩阵不能由全零矩阵得到

解法一：可能是我能想到的最复杂的方法

1）将二维数组根据行优先原则，变为一维数组。

2）然后对一维数组进行排序，取不为零的值，将元素对应的值拆分成对应个数该元素，然后全排列。这样得到所有可能的矩阵元素递减策略。例如A[0][0] = 3则对应A[0]拆分成3个A[0]

3）对上述排列逐一判断

1>如果相邻元素在二维数组中不“相邻”则排除

2>如果同一个元素相邻则排除

3>遍历到某个排列时，正好遍历完则返回正确

如果遍历完整个全排列，也没有得到正确结果，则说明不能由全零矩阵得到整形 矩阵 解法二：优化解法一

1）先扫描整个二维数组，如果某个元素值大于其周围元素值和，则返回错误

2）然后利用动态规划，递归的思路。

自己写的递归算法，不知有无错误。敬请斧正！！！谢谢！！！

#include <iostream>
using  namespace std;
#define cols 2
#define rows  2
int test(int a[][cols])
{
	int n=0;
	for(int i=0;i<cols;++i)
	{
		for(int j=0;j<rows;++j)
		{
			if(a[i][j]==0)
			    ++n;
		}
	}
	if(n==cols*rows)
	{
		//cout<<""<<endl;
		return 1;
	} 
	
}
int aroundTest(int a[][cols],int i,int j)
{
	int flag=0;
            	if((i-1>=0)&&(j-1>=0)&&(a[i-1][j-1]>0))
				{
					flag=1;
					a[i-1][j-1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i-1,j-1);
					a[i-1][j-1]++;
				}	
				if((i-1>=0)&&(a[i-1][j]>0))
				{
					flag=1;
					a[i-1][j]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i-1,j);
					a[i-1][j]++;
				}	
				if((i-1>=0)&&(a[i-1][j+1]>0))
				{
					flag=1;
					a[i-1][j+1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i-1,j+1);
					a[i-1][j+1]++;
				}	
				if((j-1>=0)&&(a[i][j-1]>0))
				{
					flag=1;
					a[i][j-1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i,j-1);
					a[i][j-1]++;
				}	
				if((a[i][j+1]>0))
				{
					flag=1;
					a[i][j+1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i,j+1);
					a[i][j+1]++;
				}	
				if((a[i+1][j-1]>0))
				{
					flag=1;
					a[i+1][j-1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i+1,j-1);
					a[i+1][j-1]++;
				}	
				if((a[i][j+1]>0))
				{
					flag=1;
					a[i][j+1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i,j+1);
					a[i][j+1]++;
				}	
				if((a[i+1][j+1]>0))
				{
					flag=1;
					a[i+1][j+1]--;
					if(test(a)==1)
					   return 1;
					aroundTest(a,i+1,j+1);
					a[i+1][j+1]++;
				}	
				
	if(flag==0)
		return 0;	
}
void distiguish(int a[][cols])//i为行，n为每行元素个数 
{
	int result;
	for(int i=0;i<cols;i++)
	{
		for(int j=0;j<rows;j++)
		{
			if(a[i][j]<0)
			{
				cout<<"False"<<endl;
				return; 
			}
			else if(a[i][j]>0)
			{
				a[i][j]--;
				result=aroundTest(a,i,j);
				if(result==1)
				{
					cout<<"YES"<<endl;
					return; 
				}
				else
				{
					cout<<"NO"<<endl;
					return; 
				}
				
			}
			else if(a[i][j] == 0)
			{
				if(test(a) == 1)
			    {
				  cout<<"YES"<<endl;
				  return; 
 				} 
			  
			}
		}
	}
	
}

int main()
{
	int a[][2]={{0,1},{1,1}};
	distiguish(a);
	
}

附：退出单重循环用break；

退出双重或多重循环用return；

二，一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值
比如{3，2，4，3，6}可以分成{3，2，4，3，6} m=1;
{3,6} {2,4,3} m=2
{3,3} {2,4} {6} m=3

所以m的最大值为3

分析：1）如果所有值的和sum(a[0]-a[n])/m ！= 0则直接退出

如果数组最大值>sum/m 则m不能再增加了

2）主要用的思想为，深度优先遍历，优化用剪枝法。

对于 递归算法 bool dfs(int res,int cpl,int level)

res为当前要凑齐长度的数组中，已经添加元素后的长度

cpl 为已经添加好的组数

每次先判断当前数组是否已经符合分组条件，符合则cpl+1

添加某个未使用的元素有三种情况

1>添加后等于分组后每组大小 这时试着添加后，进行递归。如果最终返回true则成功，否则，不能添加本元素到当前小组

2>添加后小于分组后大小 ，也试着添加，然后同上

3>添加后大于分组后大小，则舍弃

如果全程没有返回一个ture则该分组不正确

代码：

#include<iostream>
#include<algorithm>
using namespace std;
int n;              //小棒总数
int len;            //当前枚举的原棒长度
int parts;          //当前组合的原棒数
int max;            //最长小棒的长度
int sum;            //所有小棒的总长
int a[100];       //存储小棒相关信息
bool used[100];      //标记小棒是否使用

bool pt(int a,int b)
{
 	return a>b;
}
//res 为每组长度和  cpl 为组数 
bool dfs(int res,int cpl,int level)//res:当前已组合进去的木棒的长度      cpl:组合进去的小木棒的条数
{
    int i;
    if(res==len)//本组够长 
    {
        res = 0;
        cpl++;
    }
    if(cpl == parts)//组数已够 
        return true;
        
    for(i=level;i<n;i++)
    {
        if(i && !used[i-1] && a[i]==a[i-1])
			continue;
        if(used[i]==0)//该棒没有用 
        {
            if(res + a[i] <len) //如果添加该棒 没有超过长度则添加之 
            {
                used[i] = true;
                if(dfs(res+a[i],cpl,i+1)) //添加后测试其余 
					return true;
                used[i] = false;//说明上述添加失败 
            }
            else if(res+a[i]==len)//添加后刚好相等 
            {
                used[i] = true;
                if(dfs(0,cpl+1,0))//进行剩下数组的划分 
					return true;
                used[i] = false; //走到这里说明，上述失败需要回溯 
            }
            if(res==0) 
				break;
        }
        
        
    }
    return false;    
}
int main()
{
    int i;

    n=5; //元素个数 
    //int b[]={4,4,4,4};
    int b[]={3,2,4,3,6};
    
    for(int j=0;j<n;++j)//初始化数组 
          a[j]=b[j];
	

        sum=0;
        for(i=0;i<n;i++)
		{
            sum+=a[i];
            used[i]=false;
        }
        sort(a,a+n,pt);//从大到小排序
		 
	    int m=1;
	    int max=1;
   
	    
	    for(m=2;m<=n;m++)
	    {
	    	 for(i=0;i<n;i++)
			{
            
            		used[i]=false;
		    }
        
    		if(sum%m==0)//可以整除 
    		{
    			  
		    	len=sum/m;
		    	parts=m;
	    	
       		   if(dfs(0,1,0))
        		{
            		//printf("yes\n");
            		max=m;
   				}
  			 
			
		    }
    		
    	}
    	cout<<max<<endl;
    
  return 0;
}