良心数据~

思路

首先化简题意，题目要把方格划分为两个集合，每个集合必须联通，我们不妨把这个问题转化为寻找这两个集合的分界线，又因要求两个集合都要有在边界上的方格，分界线一定是起于边缘终于边缘的。

此时注意到$n\leq 6,m\leq 7$，考虑将方格图转化为$(a+1)\times (b+1)$的网格图，然后暴力枚举边界线。

注意事项

1.一定要开vis数组，边界线不能与自己有交点

2.不能使用记忆化搜索，因为vis数组的内容对答案有影响（话说你差这一点时间吗？）

3.一定要在判断边界之后再赋值vis数组，要不然一个边界顶点只会访问一次

4.最后ans记得除$2$！！！边界线的方向记得消除！！！

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=10;//这是什么？
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int n,m;
bool v[N][N];
int dfs(int x,int y)
{
	if(v[x][y])return 0;
	if(x==1||y==1||x==n||y==m)return 1;
	v[x][y]=1;
	int res=0;
	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)
		{
			res+=dfs(xx,yy);
		}
	}
	v[x][y]=0;
	return res;
}
int main()
{
	scanf("%d%d",&n,&m);n++,m++;
	int ans=0;
	for(int i=2;i<n;i++)
	{
		v[i][1]=1;
		ans+=dfs(i,2);
		v[i][1]=0;
	}
	for(int i=2;i<n;i++)
	{
		v[i][m]=1;
		ans+=dfs(i,m-1);
		v[i][m]=0;
	}
	for(int i=2;i<m;i++)
	{
		v[1][i]=1;
		ans+=dfs(2,i);
		v[1][i]=0;
	}
	for(int i=2;i<m;i++)
	{
		v[n][i]=1;
		ans+=dfs(n-1,i);
		v[n][i]=0;
	}
	printf("%d\n",ans/2);
	return 0;
}

话说这个数据太小了，考虑进行打表

#include<bits/stdc++.h>
using namespace std;
int ans[7][8]={{0,0,0,0,0,0,0,0,},{0,0,1,2,3,4,5,6,},{0,1,6,15,28,45,66,91,},{0,2,15,52,143,350,799,1744,},{0,3,28,143,614,2431,9184,33603,},{0,4,45,350,2431,16000,102147,637330,},{0,5,66,799,9184,102147,1114394,11948355}};
int main()
{
	int n,m;scanf("%d%d",&n,&m);
	printf("%d\n",ans[n][m]);
}

题意简述：

求用一条 路（经过网格线，而不是方格） 将 $a\times b$ 的矩形分为 非空的 两部分的方案数。

题目解法：

发现最后形成的路一定碰到边界。

那么对于这个由 $a\times b$ 个小正方形组成的方格进行 重新编号，对于原先的正方形 $(x,y)$，规定它的右下角为 $(x,y)$，左上角为 $(x-1,y-1)$。这样，就变成了一张 $(n+1)\times (m+1)$ 的 网格图。

由于 $n,m$ 较小在这张 $(n+1)\times (m+1)$ 的 网格图 上用 $\rm dfs$ 进行统计即可。

如果 $n,m\le12$，则需用插头 $\rm DP$ 等神仙算法进行计算，类似 从方格这头走向那头有多少种走法呢。

正确代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int res=0;
    char c;
    bool zf=0;
    while(((c=getchar())<'0'||c>'9')&&c!= '-');
    if(c=='-')zf=1;
    else res=c-'0';
    while((c=getchar())>='0'&&c<='9')res=(res<<3)+(res<<1)+c-'0';
    if(zf)return -res;
    return res;
}
int n,m;
bool vis[7][8];
int ans;
const int dx[]={0,0,-1,1},dy[]={-1,1,0,0};
void dfs(int x,int y){
	if(!x||!y||x==n||y==m){
		ans++;
		return;
	}
	vis[x][y]=1;
	for(register int i=0;i<4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(vis[xx][yy]){
			continue;
		}
		dfs(xx,yy);
	}
	vis[x][y]=0;
	return;
}
signed main(){
	n=read(),m=read();
	for(register int i=1;i<n;i++){
		vis[i][0]=1;
		dfs(i,1);
		vis[i][0]=0;
	}
	for(register int i=1;i<m;i++){
		vis[0][i]=1;
		dfs(1,i);
		vis[0][i]=0;
	}
	cout<<ans<<'\n';
	return 0;
}

如果您没有看懂这篇题解，可以在评论区问我，我将会回答您的问题并且修改这篇题解，使它变得更加通俗易懂，服务更多的 $\text{OIer}$。
如果您看懂了这篇题解，可以点个赞，使这篇题解的排名上升，服务更多的 $\text{OIer}$。