[Blue Bridge Cup 2017 preliminary] grid division

subject

analysis

Because every plan goes through the middle point (3,3), So we can (3,3) Start the minute 2 A direction Search for （ And this 2 The direction is symmetrical , So when one direction reaches the boundary , The other will also reach the border , That is an answer ）

Reference code

#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)
{
    
	//  Meeting the boundary is a solution  
	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） About （3,3） Symmetrical points  
		
		if(x1 < 0 || x1 > 6 || y1 < 0 || y1 > 6 || st[x1][y1]) continue;
		
		st[x1][y1] = st[x2][y2] = true; //2 Two symmetrical points are marks  
		dfs(x1, y1);
		st[x1][y1] = st[x2][y2] = false; // to flash back  
	}
}

int main()
{
    
	st[3][3] = true;
	dfs(3, 3);
	cout << ans / 4 << endl; //  Because up and down , Both sides are symmetrical , So divide and 4 
	return 0;
}