勉强通过测试没办法解决两行两列问题的c++代码

解题思路:首先确定该题目是属于数据结构中的连通图的遍历问题，想到要使用dfs即深度优先遍历，属于一个递归，回溯和剪枝问题

注意事项:要注意递归循环时需要在设置一个数组来标记该点有没有被访问过，否则会出现再次回到已访问的点的情况，我的代码只能勉强通过测试但是没办法解决

2 2

1 2

3 6

这种情况

参考代码:

#include<stdio.h>

#include<iostream>

#include<algorithm>//使用min()函数需要加的头文件

using namespace std;

int m,n;//定义为全局变量

int total=0;

int a[10][10];//怎么

int ans=100;

int visited[10][10];

void f(int i,int j,int sum,int cnt)//深搜，找什么在变化，总数在变，坐标在变，计数在变,坐标向四个方向变化

{

if(sum>total/2) return ;

if(sum==total/2)

{ ans=min(ans,cnt);

return ;}

visited[i][j]=1;

//可以有四个分支

if(i+1<n&&visited[i+1][j]==0)//跑到最后一行只能往左右走，采用递归调用，还要考虑可能会有再次回到出发点的情况，加一个数组来标志着有没有被访问过

{f(i+1,j,sum+a[i][j],cnt+1);}

if(j+1<m&&visited[i][j+1]==0){f(i,j+1,sum+a[i][j],cnt+1);}

if(i-1>=0&&visited[i-1][j]==0){f(i-1,j,sum+a[i][j],cnt+1);}

if(j-1>=0&&visited[i][j-1]==0){f(i,j-1,sum+a[i][j],cnt+1);}

visited[i][j]=0;

}

int main()

{

int i,j;

cin>>m>>n;

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

{

cin>>a[i][j];

total+=a[i][j];

visited[i][j]=0;//没走过是0

}

}

f(0,0,0,0);

printf("%d",ans);

}