【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;
}