拼接
题目 拼接
思路分析
暂时没有头绪 什么才算能拼成呢 还得旋转
啧 这题主要是卡在了思路上 多模拟下案例会发现和方格分割很像
由于要将矩阵分割成两部分，且旋转后依旧要完美匹配；
因此被分割的两块都必须是沿着主对角线对称的！！！
对于这一点 可以多画几组图
对于找规律的题 要大胆猜测 多画图
案例都不模拟 你怎么找到规律？
那么问题就转变成了——以对角线上的每一个点为起点，在搜索的过程中同时标记搜索点和对称点，当触及边界时，就完成了一次分割；
从之前的中心对称 变成了 对角线对称
左边的上对应对称的右
右对应上
下对应左
左对应下
即 ab对应ba
ok 接下来就和方格分割一样了 dfs解决
另外要注意的一点是 不能走对角线 也不能跨对角线 所以只有到左边界或到上边界才表示停止 并没有到右下边界停止的情况
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=10;
int cnt=0;
bool st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool isVaild(int x,int y){
return x>=0 && x<=7 && y>=0 && y<=7 && !st[x][y];
}
void dfs(int x,int y){
if(x==0 || y==7){
cnt++;
return;
}
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(isVaild(nx,ny) && isVaild(ny,nx) && nx!=ny){
st[nx][ny]=st[ny][nx]=true;
dfs(nx,ny);
st[nx][ny]=st[ny][nx]=false;
}
}
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=0;i<=7;i++)
{
st[i][i]=true;
dfs(i,i);
st[i][i]=false;
}
cout<<cnt;
return 0;
}
💬 评论