题解 P4537 【[CQOI2007]矩形】

hhoppitree · 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}。