昨天晚上看了一个题目，这个题目很强，一开始在做的时候，没有考虑那么多，想来想去还是没有什么头绪，后来看到一个哥们写的题目发现特别简单，但是特别难懂，后来查了一下相关资料，哇，确实是一个强题，可能一般人来看这个题目的话，代码可能会写很多，而且效率也不算很高，但是这个标准解答还是很不错的。题目如下。

结果为0的序列：

考虑由1到n(n<=9)按递增顺序排成的序列1234...n,在他们之间加入加号，减号或者什么也不加，分别使它们做加法，减法或者将数字合并。然后求出结果，看看是否为0。

写一个程序，找出所有长度为n的结果为0的序列,返回序列的个数。

函数接口：int ResultIsZero(int n);

其中n表示序列的长度，int表示返回的序列的个数。

举例：

n = 8，返回10。

序列分别为：

1+2+3+4-5-6-7+8 = 0;

1+2+3-4+5-6+7-8 = 0;

1+2-3+4+5+6-7-8 = 0;

1+2-3-4-5-6+7+8 = 0;

1-2+3-4-5+6-7+8 = 0;

1-2-3+4+5-6-7+8 = 0;

1-2-3+4-5+6+7-8 = 0;

1+23-45+6+7+8 = 0;

12-34-56+78 = 0;

1-23-4+5+6+7+8 = 0;

如果你看明白了题目，你可以开始做这个题目了，如果你看明白了但是想了半天和我一样不会做的话，那就需要先来了解一下深度优先搜索DFS了。

了解百度百科，还有一个详细资料，关于图论的，关于迷宫的深度搜索算法。下面我给出一个迷宫的算法，迷宫如下图所示。

迷宫的代码如下：

Code#region Code

#include <iostream>
using std::cout;
using std::endl;

int n[5][5];

int init()
...{
    n[0][0]=1;
    n[0][1]=1;
    n[0][2]=1;
    n[0][3]=1;
    n[0][4]=0;
    n[1][0]=1;
    n[1][1]=0;
    n[1][2]=1;
    n[1][3]=1;
    n[1][4]=1;
    n[2][0]=1;
    n[2][1]=1;
    n[2][2]=1;
    n[2][3]=0;
    n[2][4]=1;
    n[3][0]=0;
    n[3][1]=1;
    n[3][2]=0;
    n[3][3]=0;
    n[3][4]=0;
    n[4][0]=0;
    n[4][1]=1;
    n[4][2]=1;
    n[4][3]=1;
    n[4][4]=1;
    return 0;
}

int find(int x,int y)
...{
    cout<<x<<"\t"<<y<<endl;
    if(x==4&&y==4)
    ...{
        cout<<endl;
        return 1;
    }
    else if(n[x][y]==0||x>4||y>4||x<0||y<0)
    ...{
        return 0;
    }

    n[x][y]=0;
    return find(x,y+1)+find(x+1,y);
}

int main(void)
...{
    init();
    int r = find(0,0);
    cout<<r<<endl;
    return 0;
}

#endregion

我们只有了解了迷宫的深度优先的搜索的递归算法，才能再来回头看我们前面说的题目，那个找结果为0的数字的表达式集合，我们同样可以用深度优先搜索计算，代码如下所示。

Code#region Code

#include <iostream>
using std::cout;
using std::endl;

static int N;

static int ResultIsZeroDFS(int n, int total, int last)
...{
    const int current = n+1;
    int sub = total+last;
    if( n == N )
    ...{
        return (total+last == 0);
    }
    else
    ...{
        int result = ResultIsZeroDFS(current, total, last*10+current)+
                     ResultIsZeroDFS(current, total+last, current)+
                     ResultIsZeroDFS(current, total-last, current);

        return result;
    }
}

int ResultIsZero(int n)
...{
    N = n;
    return ResultIsZeroDFS(1, 0, 1);
}

int main(void)
...{
    cout<<ResultIsZero(8);
    return 0;
}

#endregion

这个答案是不是很强，其实其中还有很多值得我们去学习。。

数据结构, 趣题 dfs, 深度优先搜索