Grid division [DFS]

Topic

Ideas

dfs Split the path

Because as like as two peas, two figures are split. , So the path must pass (3, 3) This point , And the paths on both sides must be symmetrical .

So, from (3, 3) Start dfs, Mark the current point it has passed as passed , Then mark the other symmetrical side as passing through , So you can go on both sides at the same time .

Once you get to the boundary, the answer is +1

The final answer needs to be divided by 4, Because the two parts of symmetry will repeat .

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int g[N][N];
int ans = 0;
int xx[4] = {
    0, 1, 0, -1};
int yy[4] = {
    1, 0, -1, 0};
void dfs(int x, int y)
{
    
	g[x][y] = 1;
	if (x == 0 || x == 6 || y == 0 || y == 6)
	{
    
		ans ++;
		return;
	}
	for (int i = 0; i < 4; i ++ )
	{
    
		int dx = x + xx[i];
		int dy = y + yy[i];
		if (dx >= 0 && dx <= 6 && dy >= 0 && dy <= 6 && g[dx][dy] == 0)
		{
    
			g[dx][dy] = 1;
			g[6 - dx][6 - dy] = 1;
			dfs(dx, dy);
			g[dx][dy] = 0;
			g[6 - dx][6 - dy] = 0;
		}
	}
}
int main()
{
    
	/* code */
	dfs(3, 3);
	cout << ans/4 << endl;
	return 0;
}