矩形RECT是什么意思？

本文共计833个文字，预计阅读时间需要4分钟。

题目链接+题目+题目描述+给定一个a×b矩阵，由a×b个单行正方形组成。你需要沿着网格线把它分成两部分的空格，每部分都有格子连通，且至少有一个格子在原矩阵的边界上。连通是指两部分之间至少有一个格子的连通。

题目链接

题目

题目描述

给一个a*b矩形，由a*b个单位正方形组成。你需要沿着网格线把它分成分空的两部分，每部分所有格子连通，且至少有一个格子在原矩形的边界上。“连通”是指任两个格子都可以通过水平或者竖直路径连在一起。 求方案总数。例如3*2的矩形有15种方案。

输入描述

输入仅一行，为两个整数a，b。\(1\leq a\leq6\) ，\(2\leq b\leq 7\)

输出描述

输出仅一行，即方案总数。

示例1

输入

3 2

输出

15

示例2

输入

3 3

输出

52 题解

知识点：DFS。

计数问题用dfs较为合适，注意到只要切成两块，因此切入点和切出点各仅有一个，而且切痕不能交叉。因此枚举各边的切入点，搜索所有切痕条数，切出边一次算一条（包括自己边）。