链接：

//这一次是搜索全场.......哎~感觉BFS还行，但DFS不是很懂啊.............= =

A.A Knight's Journey

据说是很经典但也是很水的DFS题目~

题意：在一个p*q的棋盘上，一个knight要环游棋盘 ，每个点只走一遍，要历遍所有的点，问是否可能，若不可以则输出impossible，反之输出坐标。

注：在题目中要求按字典树输出，故要注意坐标点~按下图的序号走，则从(A,1)开始历遍，第一次成功的就是按字典树排列的点~

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 const int add[8][2]={
   {-2,-1},{-2,1},{-1,-2},{-1,2},{
   1,-2},{
   1,2},{
   2,-1},{
   2,1}}; 7 int a[27][27],p,q,judge,step; 8  9 class K10 {11 public:12     int x,y;13 }knight[100];14 15 void DFS(int x,int y)16 {17     if(judge) return;18     int i,hx,hy;19     knight[step].x=x;20     knight[step].y=y;21     step++;22     if(step==p*q)23     {judge=1;return;}24     a[x][y]=1;25     for(i=0;i<8;i++)26     {27         hx=x+add[i][1];28         hy=y+add[i][0];29         if(hx>=0 && hx
        
=0 && hy26) {printf("impossible\n\n");continue;}49         memset(a,0,sizeof(a));50         memset(knight,0,sizeof(knight));51         judge=0;52         step=0;53         DFS(0,0);54         if(judge)55         {56             for(i=0;i
       
      
     

B.Avoid The Lakes

很简单~~~BFS

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int a[100][100],maxx,X,Y,G,number; 7 int add[4][2]={
   {-1,0},{
   1,0},{
   0,1},{
   0,-1}}; 8  9 class O10 {11 public:12     int x,y;13 }q[10025];14 15 void bfs(int x,int y)16 {17     int f=0,r=1,hx,hy,i;18     memset(q,0,sizeof(q));19     q[0].x=x;20     q[0].y=y;21     a[x][y]=0;22     number=1;23     while(f<=r)24     {25         for(i=0;i<4;i++)26         {27             hx=q[f].x+add[i][1];28             hy=q[f].y+add[i][0];29             if(hx>=0 && hx
        
         =0 && hy
         
          maxx) maxx=number;40     return;41 }42 43 int main()44 {45     while(scanf("%d%d%d",&X,&Y,&G)!=EOF)46     {47         int i,j,k;48         memset(a,0,sizeof(a));49         for(k=0;k
         
        
       
      
     

 C.Dungeon Master

比较简单~是一道三维的BFS题目~只要注意三维字符串的输入即可，其它的跟二维相同~

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int number,Z,X,Y,x1,y1,z1,x2,y2,z2; 7 const int add[6][3]={
   {
   0,1,0},{
   0,-1,0},{
   1,0,0},{-1,0,0},{
   0,0,1},{
   0,0,-1}}; 8 char a[30][30][30]; 9 10 class K11 {12 public:13     int x,y,z,step;14 }k[1000000];15 16 void bfs(int z,int x,int y)17 {18     int f=0,r=1,i,hx,hy,hz;19     k[0].x=x;20     k[0].y=y;21     k[0].z=z;22     k[0].step=0;23     a[z][x][y]='#';24     k[1000000]={
   0};25     while(f
        
         =0 && hx
         
          =0 && hy
          
           =0 && hz
          
         
        
       
      
     

D.Sum It Up

DFS~

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int N,t,judge,a[10000],k[10000]; 7  8 void DFS(int sum,int x,int step) 9 {10     int i;11     if(sum>N) return;12     if(sum==N)13     {14         printf("%d",k[0]);15         for(i=1;i
        
         N)  continue;25         if(a[i]!=last)                              //重点！！！！last代表跳出的数，避免出现相同式子！！26         {27             last=k[step]=a[i];28             DFS(sum+a[i],i+1,step+1);29         }30    }31 }32 33 int main()34 {35     while(~scanf("%d%d",&N,&t),N,t)36     {37         int i;38         memset(a,0,sizeof(a));39         memset(k,0,sizeof(k));40         for(i=0;i
        
       
      
     

 

E.N皇后问题

由于数据很小，SO.........采用枚举水过的代码：

1 #include
     
       2 #include
      
        3 using namespace std; 4 int main() 5 { 6     int i,sum; 7     while(~scanf("%d",&i),i) 8     { 9         if(i==1)10            sum=1;11         if(i==2 || i==3)12             sum=0;13         if(i==4)14             sum=2;15         if(i==5)16             sum=10;17         if(i==6)18             sum=4;19         if(i==7)20            sum=40;21         if(i==8)22             sum=92;23         if(i==9)24             sum=352;25         if(i==10)26             sum=724;27        cout<
       
        <
       
      
     

正解：

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 #define N 15 7 int n; 8 int sum; 9 int x[N],b[N];10 11 12 int place(int k)13 {14     int i;15     for(i=1;i
        
         n && n>0) //当放置的皇后超过n时，可行解个数加1，此时n必须大于025           sum++;26       else27       for(int i=1;i<=n;i++)28       {29           x[t] = i; //标明第t个皇后放在第i列30           if(place(t)) //如果可以放在某一位置，则继续放下一皇后31             queen(t+1);32       }33     return sum;34 }35 36 int main()37 {38     int t,i;39     for(i=1;i<=10;i++)40     {41         sum=0;42         n=i;43         b[i]=queen(1);44     }45     while(scanf("%d",&n),n)46     {47         printf("%d\n",b[n]);48     }49     return 0;50 }
        
       
      
     

源代码：

在此基础上做了一小部分改动.........

F.Basic

是变形的N皇后问题~

在每一个能放棋子的点，作为第一个放棋子的点，看能放多少棋子，输出最多能放的棋子数~

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int n,number; 7 char a[10][10]; 8  9 int judge(int x,int y)                           //判断该点能否放棋子，在遇到X前，该点所对应的横排和竖排是否有0点，若有则不能放棋子10 {11     int i;12     for(i=x+1;i<=n && a[i][y]!='X';i++)13         if(a[i][y]=='0')   return false;14     for(i=x-1;i>=1 && a[i][y]!='X';i--)15         if(a[i][y]=='0')   return false;16     for(i=y+1;i<=n && a[x][i]!='X';i++)17         if(a[x][i]=='0')   return false;18     for(i=y-1;i>=1 && a[x][i]!='x';i--)19         if(a[x][i]=='0')   return false;20     return true;21 }22 23 void DFS(int x,int y,int step)               24 {25     int i,j;26     for(i=1;i<=n;i++)27         for(j=1;j<=n;j++)28         if(a[i][j]=='.' && judge(i,j))29     {30         a[i][j]='0';31         DFS(i,j,step+1);32         a[i][j]='.';33     }34     if(number
       
      
     

 

G.Asteroids!

与第三题很相似，也是三维的BFS~

代码如下：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int number,quan,N,x1,y1,z1,x2,y2,z2; 7 const int add[6][3]={
   {
   0,1,0},{
   0,-1,0},{
   1,0,0},{-1,0,0},{
   0,0,1},{
   0,0,-1}}; 8 char a[30][30][30]; 9 10 class K11 {12 public:13     int x,y,z,step;14 }k[1000000];15 16 void bfs(int z,int x,int y)17 {18     int f=0,r=1,i,hx,hy,hz;19     memset(k,0,sizeof(k));20     k[0].x=x;21     k[0].y=y;22     k[0].z=z;23     k[0].step=0;24     a[z][x][y]='X';25     while(f
        
         =0 && hx
         
          =0 && hy
          
           =0 && hz