2017年第八届蓝桥杯 - 省赛 - C/C++大学A组 - D. 方格分割
6x6的方格，沿着格子的边线剪开成两部分。
要求这两部分的形状完全相同。
如图：p1.png, p2.png, p3.png 就是可行的分割法。
试计算：包括这3种分法在内，一共有多少种不同的分割方法。
注意：旋转对称的属于同一种分割法。
请提交该整数，不要填写任何多余的内容或说明文字。
Ideas“一共有多少种不同的分割方法” ，想到DFS。
要求是沿着格子的边线剪开成形状完全相同的两部分，并且通过例子我们可以发现，两部分图形其实是中心对称的，所以我们可以在DFS进行搜索的时候就处理好对称。
还要注意，“旋转对称的属于同一种分割法”，一种切割方案可以进行旋转90°、180°、270°，相当于计算了4次，所以最终得到的方案数要除以4。
Code C++#include using namespace std; int dire[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int visited[7][7],ans; void dfs(int x,int y) { if(x==0||y==0||x==6||y==6) { ans++; return ; } visited[x][y]=1; visited[6-x][6-y]=1; for(int k=0;k<4;k++) { int nx=x+dire[k][0]; int ny=y+dire[k][1]; if(nx<0||nx>6||ny<0||ny>6) continue; if(!visited[nx][ny]) dfs(nx,ny); } visited[x][y]=0; visited[6-x][6-y]=0; } int main() { dfs(3,3); cout<<ans/4<<endl; return 0; }
Python
def dfs(x: int, y: int): if x == 0 or y == 0 or x == 6 or y == 6: global ans
ans += 1 return vis[x][y] = True vis[6 - x][6 - y] = True for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]: nx, ny = x + dx, y + dy if -1 < nx < 7 and -1 < ny < 7 and not vis[nx][ny]: dfs(nx, ny) vis[x][y] = False vis[6 - x][6 - y] = False if __name__ == '__main__': ans = 0 vis = [[False for _ in range(7)] for _ in range(7)] dfs(3, 3) print(ans // 4)
Answer：509
在线评测：https://www.lanqiao.cn/problems/1629/learning/
