Blue Bridge Cup Winter vacation homework (DFS backtracking + pruning)

Question:

Result:64

Solve:

DFS to flash back , Just try one by one and fill in a few , And then TLE 了

Two questions ：

First of all ： Run completely 13 Try a few , Will be Fried , We need to get rid of the impossible plan in advance , For example, fill in the first line , I'll see if the first formula works

second ： Division in the standard answer of this question is only divisible , instead of “/”, Then it led me to look at my 1376 Dazed for a long time , Great speechless event

Code:

#include <bits/stdc++.h>
using namespace std;
bool a[14];
int num[13];
int res = 0;
void dfs(int deep)
{
	// Remove in advance  
	if(deep > 3 && num[1] + num[2] != num[3])return ;
	if(deep > 6 && num[4] - num[5] != num[6])return ;
	if(deep > 9 && num[7] * num[8] != num[9])return ;
	// Final judgment  
	if(deep > 12)
	{
		if(num[10] / num[11] == num[12] && num[10]%num[11] == 0)
			res++;
			
		return ;
	}
	// Search for  
	for(int i = 1; i <= 13; i++){
		if(a[i] == true) continue;
		num[deep] = i; a[i] = true;
		dfs(deep+1);
		// to flash back  
		a[i] = false;
	}
}
int main(void)
{
	memset(a,false,sizeof(a));
	dfs(1);
	cout <<res;
	return 0;
}

Statement ： The pictures are from the official website of the Blue Bridge Cup , For the purpose of sorting out personal questions , In case of infringement , Please contact to delete ~