题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(递归搜索) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstdio>
//蓝桥杯官网可以过,一个dfs模板,记录步数并判断
using namespace std;
const int N = 15;
int a[N][N],n,m,sum,minx=110;
bool st[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
//返回数目
void dfs(int x,int y,int z,int d)
{
if(z>sum/2) return;
if(z==sum/2) {minx=min(minx,d);return;}
for(int i=0;i<4;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!st[xx][yy])
{
st[xx][yy]=true;
dfs(xx,yy,z+a[xx][yy],d+1);
st[xx][yy]=false;
}
}
}
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&a[i][j]);
sum+=a[i][j];
}
//这个判断只能过一个样例
if(sum%2) puts("0");
else
{
st[1][1]=true;
dfs(1,1,a[1][1],1);
if(minx==110) puts("0");
else cout << minx << endl;
}
return 0;
}