题意简述:
求用一条 路(经过网格线,而不是方格) 将 $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}$。