矩形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较为合适，注意到只要切成两块，因此切入点和切出点各仅有一个，而且切痕不能交叉。因此枚举各边的切入点，搜索所有切痕条数，切出边一次算一条（包括自己边）。

由于枚举时会产生重复情况，因为路径的终点也能作为起点返回去算一条，但结合矩形的对称性，我们枚举横竖两边即可。先给边标号 \(1,2,3,4\) ，假设 \(1,2\) 是横竖两边，那么能搜索出 \(11,11,12,13,14;21,22,22,23,24\) 边上所有点的切线条数，其中 \(11,22\) 有两次是因为自己边作为起点和终点可以有往返两条路径。我们把其中 \(11\) 作为 \(33\) ，\(22\) 作为 \(44\) ，\(21\) 作为 \(34\) 即可有边的全部组合。

时间复杂度 \(O(2^{mn})\)

空间复杂度 \(O(mn)\)

代码

#include <bits/stdc++.h> using namespace std; int n, m; bool vis[7][8]; const int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} }; int cnt; void dfs(int x, int y) { if (!x || !y || x == n || y == m) { cnt++; return; } for (int i = 0;i < 4;i++) { int xx = x + dir[i][0]; int yy = y + dir[i][1]; if (vis[xx][yy]) continue; vis[xx][yy] = 1; dfs(xx, yy); vis[xx][yy] = 0; } } int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; ///只需枚举横竖两条边，因为自己一边或者横竖两边之间任意路径，都会有一个重复的返回路径 ///根据对称性,可以看作对边自己或者对边横竖之间的所有路径 for (int i = 1;i < n;i++) { vis[i][0] = 1; vis[i][1] = 1; dfs(i, 1); vis[i][0] = 0; vis[i][1] = 0; } for (int i = 1;i < m;i++) { vis[0][i] = 1; vis[1][i] = 1; dfs(1, i); vis[0][i] = 0; vis[1][i] = 0; } cout << cnt << '\n'; return 0; }