第七届蓝桥杯软件类省赛真题-C-B-6_方格填数

//第七届蓝桥杯软件类省赛真题-C-B-6_方格填数 /*方格填数如下的10个格子   +--+--+--+   |  |  |  |+--+--+--+--+|  |  |  |  |+--+--+--+--+|  |  |  |+--+--+--+（如果显示有问题，也可以参看【图1.jpg】）填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。*//*【解题思路】解法：暴力枚举或深度优先搜索，其中需注意条件不能漏，应细心 答案：11318*/#include<iostream>#include<cmath> using namespace std;double a[10];bool visit[10];int count = 0;void dfs(int step){	if(step == 10)	{		if(abs(a[0]-a[4]) != 1.0 && abs(a[0]-a[1]) != 1.0 && abs(a[0]-a[3]) != 1.0 && abs(a[0]-a[5]) != 1.0			&& abs(a[1]-a[5]) != 1.0 && abs(a[1]-a[2]) != 1.0 && abs(a[1]-a[4]) != 1.0 && abs(a[1]-a[6]) != 1.0				&& abs(a[2]-a[6]) != 1.0 && abs(a[2]-a[5]) != 1.0					&& abs(a[3]-a[7]) != 1.0 && abs(a[3]-a[4]) != 1.0 && abs(a[3]-a[8]) != 1.0						&& abs(a[4]-a[8]) != 1.0 && abs(a[4]-a[9]) != 1.0 && abs(a[4]-a[7]) != 1.0							&& abs(a[5]-a[9]) != 1.0 && abs(a[5]-a[6]) != 1.0 && abs(a[5]-a[8]) != 1.0								&& abs(a[6]-a[9]) != 1.0){									count++;//									cout<<"  "<<a<<" "<<b<<" "<<c<<endl;//									cout<<d<<" "<<e<<" "<<f<<" "<<g<<endl;//									cout<<h<<" "<<i<<" "<<j<<endl;//									cout<<"============"<<endl;		}		return;	}	for(int i = 0;i < 10;i ++)	{		if(visit[i] == false)		{			a[step] = i+1;			visit[i] = true;			dfs(step+1);			visit[i] = false;		}	}	return;}int main(){	dfs(0);	cout<<"这个算式共有的解法种数为："<<count<<endl;	return 0;}/*#include<iostream>#include<cmath>using namespace std;int main(){	int a,b,c,d,e,f,g,h,i,j;	int count = 0;	for(a = 0;a <= 9;a++)		 for(b = 0;b <= 9;b++)		 	for(c = 0;c <= 9;c++)		 		for(d = 0;d <= 9;d++)		 			for(e = 0;e <= 9;e++)		 				for(f = 0;f <= 9;f++)		 					for(g = 0;g <= 9;g++)		 						for(h = 0;h <= 9;h++)		 							for(i = 0;i <= 9;i++)										for(j = 0;j <= 9;j++){			 								if(a != b && a != c && a != d && a != e && a != f && a != g && a != h && a != i && a != j											  && b != c && b != d && b != e && b != f && b != g && b != h && b != i && b != j											   && c != d && c != e && c != f && c != g && c != h && c != i && c != j											    && d != e && d != f && d != g && d != h && d != i && d != j												 && e != f && e != g && e != h && e != i && e != j												  && f != g && f != h && f != i && f != j												   && g != h && g != i && g != j												    && h != i && h != j													 && i != j){												    													    	if(abs(a-e) != 1.0 && abs(a-b) != 1.0 && abs(a-d) != 1.0 && abs(a-f) != 1.0														 && abs(b-f) != 1.0 && abs(b-c) != 1.0 && abs(b-e) != 1.0 && abs(b-g) != 1.0														  && abs(c-g) != 1.0 && abs(c-f) != 1.0														   && abs(d-h) != 1.0 && abs(d-e) != 1.0 && abs(d-i) != 1.0														    && abs(e-i) != 1.0 && abs(e-j) != 1.0 && abs(e-h) != 1.0															 && abs(f-j) != 1.0 && abs(f-g) != 1.0 && abs(f-i) != 1.0															  && abs(g-j) != 1.0){												    			count++;//												    			cout<<"  "<<a<<" "<<b<<" "<<c<<endl;//												    			cout<<d<<" "<<e<<" "<<f<<" "<<g<<endl;//												    			cout<<h<<" "<<i<<" "<<j<<endl;//												    			cout<<"============"<<endl;														}												    														}										}	cout<<"方案数目的总数为："<<count<<endl;	return 0;}*/