自动搬运

查看原文

来自洛谷，原作者为

	hhoppitree 成功的秘诀只有一个：加训。故古语有云：日拱一卒，功不唐捐；玉汝于成，溪达四海。

搬运于2025-08-24 22:01:07，当前版本为作者最后更新于2021-02-07 12:53:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

求用一条 路（经过网格线，而不是方格） 将 $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}$。