蓝桥杯2013年第四届真题-格子刷油漆 （C++代码）

解题思路:

注意事项:

参考代码:

#include<stdio.h>

 int n,sum=0,i,j;
 int a[2][100]={0};
 
void dfs(int x,int y,int num)
{
 int next[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,-1},{-1,1}};
 int tx,ty,k;

 if(num==2*n)
 {
           sum++;
     return;  
 }
 for(k=0;k<8;k++)
 {
  tx=x+next[k][0];
  ty=y+next[k][1];
  
  if(tx<0  ||  tx>1  ||  ty<0  ||  ty>n-1)
  {
   continue;
  }
  if (a[tx][ty]==0)
  {
   a[tx][ty]=1;
   dfs(tx,ty,num+1);
   a[tx][ty]=0;
  }
 }
 return ;
}

int main()
{
          int ii,jj;
     scanf("%d",&n);
        for(i=0;i<2;i++)
 {
  for(j=0;j<n;j++)
  {
       for(ii=0;ii<2;ii++)
           {
              for(jj=0;jj<n;jj++)
          {
                  a[ii][jj]=0;
          }
              }
             
      a[i][j]=1;
   dfs(i,j,1);
  }
 
     }
 
 printf("%d",sum);
 return 0;
}