这题实质跟全排列一样，只是多一些限制条件

import java.util.*;
public class Main{
    static int row=0;
    static int col=0;
    static int map[][];
    static int count=0;
    static void dfs(int r,int c){
        //标准全排模板
        if(r==row&&c==0){
            count++;
            return;
        }
        map[r][c]=1;
        if(!check(r,c))
            //通过三元运算符判断下一个点的位置
            dfs(c==col-1?r+1:r,c==col-1?0:c+1);
        map[r][c]=2;
        dfs(c==col-1?r+1:r,c==col-1?0:c+1);
    }
    static boolean check(int r,int c){
        //判断当前点是否合法，横向纵向是否有三个
        if(c>=2&&map[r][c-2]==1&&map[r][c-1]==1&&map[r][c]==1)
            return true;
        if(r>=2&&map[r-2][c]==1&&map[r-1][c]==1&&map[r][c]==1)
            return true;
        return false;
    }
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        row=scan.nextInt();
        col=scan.nextInt();
        map=new int[row][col];
        dfs(0,0);
        System.out.println(count);
    }
}