第七届蓝桥杯 方格填数

2016-12-22 08:08:05来源:CSDN作者:sinat_26019265人点击

     本来一道练手的题,却被坑死了  - - 

  有谁答案是65的举个手!(正确答案是1580  , 0-9不重复)


  原因在于---> 你的数组区分未填入的数是什么,我用的是二维数组

  初始化是这样的:

   int g[5][6]={{-1,-1,-1,-1,-1,-1},{-1,0,0,0,-1,-1}, {-1,0,0,0,0,-1},{-1,-1,0,0,0,-1}

                ,{-1,-1,-1,-1,-1,-1}}

   但是,你填数的时候在判断过程中是临近数不能相邻,那么一旦1与未填的内容0相比,就不能填这个1了!因此,会有少算很多情况!

   改成:

   int g[5][6]={{-2,-2,-2,-2,-2,-2},{-2,-1,-1,-1,-2,-2}, {-2,-1,-1,-1,-1,-2}, {-2,-2,-1,-1,-1,-2}

                 ,{-2,-2,-2,-2,-2,-2} };

   避免造成临近数的误会。(-2用于区分边界,-1用于区分未填的)


   DFS

   

#include<stdio.h>int g[5][6]={{-2,-2,-2,-2,-2,-2},{-2,-1,-1,-1,-2,-2}, {-2,-1,-1,-1,-1,-2}, {-2,-2,-1,-1,-1,-2},{-2,-2,-2,-2,-2,-2} };int count = 0;int dx[]={0,0,1,-1,1,-1,1,-1};int dy[]={1,-1,0,0,1,-1,-1,1};int vis[11]={0,0,0,0,0,0,0,0,0,0,0} ;int check(int n,int x,int y){    for(int i = 0;i<8;i++)	{		if(n  == g[x+dx[i]][y+dy[i]]+1 || n == g[x+dx[i]][y+dy[i]]-1)			return 0;	}	return 1; }int dfs(int n, int c){	int i,j, k;		if(c == n-1)	{		    count++;	    	printf("%d/n",count);	}	    else	{	for(i = 1;i<4;i++)	{	    for(j = 1;j<5;j++)		{		    if(g[i][j]== -2 || g[i][j] != -1)continue; // || newx< 1 || newy< 1 || newx > 4 || newy >4					    for(k = 1;k<n;k++)			{			   if(vis[k] == 0 && check(k,i,j) )			   {				vis[k] =1;				g[i][j] = k;				dfs(n,c+1);				g[i][j] = -1;                vis[k] =0;			   }			}			return 0;		}	}	}	return 0;	//printf("*");}int main(){    count = 0;      dfs(11,0);   printf("%d",count);   return 0;}

   哎 ,看了别人的才发现一个问题,这种题应该用更快的方法才行,C++  中<algorithm>里提供了一个函数为

next_permutation(begin ,end); 直接提供排序,直接改变数祖的内容;

 

   具体算法请看 方格填数 next_permutation 

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台