1320: [蓝桥杯2017初赛]方格分割(DFS)

1320: [蓝桥杯2017初赛]方格分割
主要是思维啦
由于切割后两部分要对称,切割线总会经过整个方块的中心点(3,3),从中心点出发,只需要遍历找到半条分割线,一旦走到边界点即分隔出一种,一条路结束。
但由于dfs是一条路走到黑,设置vis时要将对称点也设置成1,
走一条路的时候要在从这点出发前将这点设为走过,结束这条路之后再回溯消除前一条路走过的痕迹

#include<iostream>
#include<string.h>
using namespace std;
int vis[10][10];
int cnt=0;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
bool inside(int x,int y){
	if(x>=0&&x<=6&&y>=0&&y<=6)return true;
	else return false;
}
void dfs(int x,int y){
	if(x==0||x==6||y==0||y==6){
		cnt++;
		return;
	}
	for(int i=0;i<4;i++){
		int cx=x+dx[i];
		int cy=y+dy[i];
		int rx=6-cx;//对称的点 
		int ry=6-cy;
		if(inside(cx,cy)&&!vis[cx][cy]){//对称设置vis成1的,判断一个就好 
			vis[cx][cy]=1;	vis[rx][ry]=1;
			dfs(cx,cy);
			vis[cx][cy]=0; vis[rx][ry]=0;
		}
	}
}
int main(){
	memset(vis,0,sizeof(vis));
	vis[3][3]=1;
	dfs(3,3);
	cout<<cnt/4;
    return 0;
}
上一篇:ipv4无internet访问权限


下一篇:el-date-picker TimePicker 时间选择器