[数据结构与算法][蓝桥杯2017初赛]方格分割

题目

分析

因为每种方案都是经过中间那个点(3,3)，所以我们可以从(3,3)开始分2个方向 搜索（并且这2方向是对称的，所以当一个方向到边界，另一个也会到边界，也就是一种答案）

参考代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <algorithm>
#include <unordered_map>
#define LL long long
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define reps(i, a, b) for(int i = a; i < b; i++) 
#define pre(i, a, b) for(int i = b; i >= a; i--)
using namespace std;

typedef pair<int, int> PII;

bool st[10][10] = {0};
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int ans = 0; 

void dfs(int x, int y)
{
	// 遇到边界就是一种方案 
	if(x == 0 || x == 6 || y == 0 || y == 6)
	{
		ans++;
		return ;
	}
	
	rep(i, 0, 3)
	{
		int x1 = x + dx[i], y1 = y + dy[i]; 
		int x2 = 6 - x1, y2 = 6 - y1; //（X1,y1）关于（3，3）对称的点 
		
		if(x1 < 0 || x1 > 6 || y1 < 0 || y1 > 6 || st[x1][y1]) continue;
		
		st[x1][y1] = st[x2][y2] = true; //2个对称的点同是标记 
		dfs(x1, y1);
		st[x1][y1] = st[x2][y2] = false; //回溯 
	}
}

int main()
{
	st[3][3] = true;
	dfs(3, 3);
	cout << ans / 4 << endl; // 因为上下，左右都是对称的，所以除与4 
	return 0;
}