P1790 矩形分割

yyyyyyyf · 2018-04-07 22:10:40 · 题解

• 这道题的思路实际非常简单
• 一个由ab个小矩形组成的矩形
• 事实上可以看成一个由(a+1)(b+1)个点组成的点图
• 那么题目就可以转换为从一个边缘上的点出发，到另一个边缘点，一共有几个方案
• 为了避免重复方案的出现，我们将出发点设置在最左及最上的边上（或者最右和最下的边）
• 接下来考虑无效切割的处理（如切割(1,1)与(2,1)之间的边，这样图依然只有一个），显然，如果我们直接从边缘点开始搜索，无效切割的出现是必然的，所以我们需要做一些处理
• 首先，不将矩形的四个顶点（即边与边的交点）作为出发点，因为从顶点出发必然会导致无效切割
• 其次，我们手动将出发点走到点阵内(如从(1,1)到(1,2)),然后再进行搜索，就可以避免无效切割。这时可能会有人问，如果"手动走到的那个点"也是边缘点怎么办？我们只需要把关于边缘点的判断写在dfs开头即可。
• 最后，跳出搜索的条件就是当前位置再次到达边缘点，答案+1，回溯

  #include<bits/stdc++.h>
  using namespace std;
  #define N 10
  int n,m;
  int ans=0;
  int movex[4]={1,0,-1,0};
  int movey[4]={0,1,0,-1};
  int vis[N][N];
  void dfs(int x,int y)
  {
      vis[x][y]=1;
      if(x==1 || y==m || x==n || y==1) //到达另一个边缘点
          {
              ans++;
              vis[x][y]=0;
              return;
          }
      for(int i=0;i<4;++i)
          {
              int xx=x+movex[i],yy=y+movey[i];
              if(xx<1 || yy<1 || xx>n || yy>m || vis[xx][yy]) continue;
              dfs(xx,yy);
          }
      vis[x][y]=0;
  }
  int main()  
  {
      scanf("%d%d",&n,&m);
      n++;m++; //转换为点图
      memset(vis,0,sizeof(vis));
      for(int i=2;i<n;++i) //这么写就是为了去掉交点
          {
              vis[i][1]=1;//手动将出发点设为已访问
              dfs(i,2);//然后手动走第一步，防止无效切割
              vis[i][1]=0;//回溯
          }
      for(int i=2;i<m;++i) //同上
          {
              vis[1][i]=1;
              dfs(2,i);
              vis[1][i]=0;
          }
      printf("%d",ans);
      return 0;
  }