蓝桥杯---剪邮票---DFS的适用范围

           注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

                      图1

                          图2

                        图3

【分析】

        本题刚开始以为是一个简单DFS搜索，就考一个去重，当时以为可以3个方向遍历就能起到去重的效果，

    但最后和别人比较发现答案少了很多数据，然后开始研究别人的代码，发现了很多有趣的东西，打了这么久

    的DFS竟然不知道这题不能光一个DFS解决（也有不了解题意的原因）。越想越感觉到DFS对有些题的不适

    应性。

   DFS代码实现的功能

           （以前从没考虑过这，但是现在一考虑确实有很多代码细节，原来DFS是这么起到独特的搜索作用）

             DFS的实现是一直递归递归到走不动或满足某种条件，才会返回回溯，取消路上的标记（回溯取消，

     有些题不回溯就不用取消，这里主要讨论的回溯情况）。

             本题剪邮票类似DFS搜索方式，但又不是DFS方式。

             因为剪连续邮票，可以是一个点的多个分支，就比如最小水池数问题（只是最小水池数不用回溯）。

             DFS最多只能选择一个点的两个方向进行遍历（上个点来的方向和下个点的方向），虽然for循环看

      似枚举4个方向，但是他只能选择一个方向走，不能同时选择俩进行遍历。

 DFS的不适用范围

               当遇到要在地图中选块且需要回溯（大多是求地图满足某个条件的总数）的题目时，一个DFS就不

       能解决此类问题此题可以看出DFS不适合遍历时可以选一个点3个方向及其以上的状况，你无法确定这个

       方向选多少点和那个方向选多少个点正好N个点，取消标记也会很复杂。

              无论怎么DFS都无法实现（这里太绝对，DFS可以做到但是太难实现，一般涉及到这的就可以选择别

       的算法去实现，会比DFS做简单很多），因为每个点的不同方向可能有很多相同的点，选好了怎么回溯是

       一个难以解决的问题。就很像一个树的结点去遍历他的子树一样，你不可能把所有子树中N个结点遍历完，

      再取消标记，要想把子树中遍历标记的结点取消标记，需要另建一个数组专门保存哪些点在这次被标记了。

【代码】

#include<stdio.h>
#include<string.h>
int num,cnt,vis[10][10],book[10][10],ans[10];
int fang[4][2]={-1,0,0,-1,0,1,1,0};// 函数功能：判断选取的k个生肖是否是连续的
void dfs2(int x,int y)
{vis[x][y]=1;cnt++;for(int i=0;i<4;i++){int tx,ty;tx=x+fang[i][0];ty=y+fang[i][1];if(tx<1||tx>3||ty<1||ty>4||!book[tx][ty]||vis[tx][ty]) continue;dfs2(tx,ty);}return ;
}
// 函数功能：实现选取由k的生肖组成的所有可能，选取的生肖序号从小到大选取，起到了判重的作用
void dfs(int k)
{if(k==6){int x=(ans[1]-1)/4+1;int y=(ans[1]-1)%4+1;memset(vis,0,sizeof(vis));cnt=0;dfs2(x,y);if(cnt==5)num++;}for(int i=ans[k-1]+1;i<13;i++) // 比上一个选取的编号要大，起到判重的作用{int x=(i-1)/4+1;int y=(i-1)%4+1;book[x][y]=1;ans[k]=i;dfs(k+1);book[x][y]=0;}
}int main()
{dfs(1);printf("%d\n",num);
}

【收获】

     1.      打了这些久的DFS，一直觉得是模板没怎么去仔细思考，现在遇到了问题，仔细想来DFS代码这么

           的经典。

       2.   懂得了什么时候不是一个DFS搜索能解决的，DFS的适应范围。

       3.    许多经典的算法虽然会用但为什么会实现这个功能或者它隐藏着什么细节都需要去挖掘。

以上全是自己的思想，如果有什么不对的地方请留言，谢谢