题意

• 把一个a*b个小正方形组成的大正方形切成两块有多少种切法？

思路

• 爆搜，对于正方形a*b转化为点阵图坐标为[0,a][0,b]
• 其中(0,0)(a,0)(0,b)不能作为起点，对于每个起点，找可能的终点即可
• 由于对称性，两条对边方案重合，所以只搜索一组邻边即可
• DFS要从不在边上的点开始，把起点标为访问，所以DFS总是标记了上一个访问的点，进入后要先把当前点标记，同理，回溯也是四个方向尝试完后，把当前点取消标记

#include<bits/stdc++.h>
using namespace std;
int a,b;
long long ans=0;
int dir[4][2]={0,1,0,-1,1,0,-1,0};
int vis[8][9];
void dfs(int x,int y){
    if(x<1||y<1||x>=a||y>=b){
        ans++;
        return;
    }
    vis[x][y]=1;  
    for(int i=0;i<4;i++){
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
        if(vis[tx][ty]) continue;
        dfs(tx,ty);
    }
    vis[x][y]=0;
}
int main(){
    //对于正方形a*b转化为点阵图坐标为[0,a][0,b]
    //(0,0)(a,0)(0,b)不能作为起点，爆搜两条边即可
    scanf("%d%d",&a,&b);
    for(int i=1;i<a;i++){
        memset(vis,0,sizeof(vis));
        vis[i][0]=1;
        dfs(i,1);
    }
    for(int i=1;i<b;i++){
        memset(vis,0,sizeof(vis));
        vis[0][i]=1;
        dfs(1,i);
    }
    printf("%d",ans);
    return 0;
}