突然想起来搜索是属于图论的，那么在解决图论的过程中把搜索解决掉。没想到非递归实现一下就搞了两天。虽然有些疑问还没有解决，但感觉已经可以写总结了，与其说总结，不如说一次尝试的记录（因为有个题最后还是TLE嘛）。（求规范代码！！！@啸爷）

众所周知，DFS的常规写法是递归实现，但递归普遍慢所以可以用模拟递归栈来循环实现。这样做有两个好处，一个是循环实现要比递归实现更快，第二个是因为模拟的栈是在程序中手动开的存储空间而不是通过递归用的计算机本身的栈，相当于外挂栈，在数量巨大的DFS的过程中不会爆栈。

当然，这是传统这么认为的，第二点没什么好说的，全局变量开的数组的确可以比递归用的栈大，所以更能有效的防止爆栈。但是关于第一点，我觉得还是有待考虑的。原因是我写的两种DFS非递归实现一个超时，一个和递归实现用时一样= =。我现在还不认为是我的代码有问题，如果大家发现问题请留言，感激不尽。

先说那个和递归实现一样的那个。

因为DFS基本上就分两种，一种是以遍历全图为目的的，需要边走边标记，而回退之后不用清除标记。目的是遍历全图嘛，标记正记录了走过的位置而方便找没有走过的位置。一种以搜索路径为目的，最短路也好，恰好到达也好，找的是一条路径问题，而最大的区别就是如果发生退栈，要进行清除标记，因为退栈后，可能存在别的路径依然会访问到这个结点。

这种DFS以POJ1562为例：

先看效果，我第一次提交是用DFS的递归实现，第二次是用非递归实现，虽然两个用时一样，但是我们还是能确定非递归实现不一定要比递归慢（我只能精确到这了TAT，我目前还没遇到递归TLE，非递归过的题目，但的确遇到了非递归TLE，递归过的题目= =）。

递归代码：

#include <iostream>
#include <cstring>

using namespace std;

char mp[150][150];
int chx[] = {1,0,-1,0,1,-1,1,-1};
int chy[] = {0,1,0,-1,1,-1,-1,1};
bool bj[150][150];

void dfs(int x,int y,int n,int m)
{
    for(int i = 0;i < 8;i++)
    {
        int tx = x + chx[i];
        int ty = y + chy[i];

        if(tx >= 0 && ty >= 0 && tx < n && ty < m)
        {
            if(bj[tx][ty] == 0)
            {
                bj[tx][ty] = 1;
                if(mp[tx][ty] == '@')
                {
                    dfs(tx,ty,n,m);
                }
            }
        }
    }
}

int main()
{
    int n,m;

    while(cin >> n >> m,n)
    {
        memset(bj,0,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int ans = 0;
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(bj[i][j] == 0 && mp[i][j] == '@')
                {
                    dfs(i,j,n,m);
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}

很常规的写法，我们根据题目要求，找到‘@’就向下搜索，直到把相连的@全部标记完成，统计有几块不相连的@。

其中遇到相连的@便进入递归直到没有找到@再回退，换一个方向继续向下搜索。

而非递归实现就是模拟这个过程：

#include <iostream>
#include <cstring>

using namespace std;

struct Stack
{
    int x,y;
}s[100000];

char mp[150][150];
int chx[] = {1,0,-1,0,1,-1,1,-1};
int chy[] = {0,1,0,-1,1,-1,-1,1};
bool bj[150][150];

void dfs(int x,int y,int n,int m)
{
    int t = 0;
    Stack now,tmp;
    now.x = x;
    now.y = y;
    s[t++] = now;
    bj[x][y] = 1;
    while(t > 0)
    {
        now = s[t - 1];
        int flag = 0;
        for(int i = 0;i < 8;i++)
        {
            tmp.x = now.x + chx[i];
            tmp.y = now.y + chy[i];

            if(tmp.x >= 0 && tmp.y >= 0 && tmp.x < n && tmp.y < m)
            {
                if(bj[tmp.x][tmp.y] == 0)
                {
                    bj[tmp.x][tmp.y] = 1;
                    if(mp[tmp.x][tmp.y] == '@')
                    {
                        s[t++] = tmp;
                        flag = 1;
                        break;
                    }
                }
            }
        }

        if(flag)
            continue;
        t--;
    }
}

int main()
{
    int n,m;

    while(cin >> n >> m,n)
    {
        memset(bj,0,sizeof(bj));
        for(int i = 0;i < n;i++)
            cin >> mp[i];

        int ans = 0;
        for(int i = 0;i < n;i++)
        {
            for(int j = 0;j < m;j++)
            {
                if(bj[i][j] == 0 && mp[i][j] == '@')
                {
                    dfs(i,j,n,m);
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    return 0;
}

我们手动创建了一个栈，如果找到‘@’就更新栈顶，然后跳出各个方向的向下遍历，因为如果不跳出，就成以这个点为起点向周围各个方向搜索的类似BFS的东西了。

更新栈顶之后便以栈顶为起点继续向下搜索，但是如果向下没有找到‘@’，也就是说没法继续更新栈顶，那只能做回退处理。但是这里有个问题，当然在这种类型的DFS中并不是问题，但是再第二个类型的DFS中需要特殊处理，那就是在递归中我们可以很好实现当回退之后，换个方向继续搜索，因为刚才的路径、方向都已经在递归栈中保存了，相当于挂起，但循环模拟却没有对之前的状态进行保存处理，举个例子：从A以第1个方向走到B（并作标记），在B没有找到下路，需要回退到A，然后A重新成为栈顶继续向下遍历，理论上应该是从第2个方向继续遍历，而循环实现依旧是从第1个方向开始，原因很好理解。至于怎么改善，讲第二种DFS的时候再做叙述。

第二种DFS，以搜索路径为目的，最短路也好，恰好到达也好，找的是一条路径问题，而最大的区别就是如果发生退栈，要进行清除标记，因为退栈后，可能存在别的路径依然会访问到这个结点。我们以ZOJ2110为例，我昨天这个题卡了一下午，递归实现很顺利就A掉了，但是非递归实现到现在还是TLE，十分费解（坏了，留下阴影了，再也不会爱了TAT）。

还是先看交题记录

因为第一次写这种类型的DFS，开始的那几个WA大家请忽视= =。

其中有个AC是我实在怀疑非递归了（一开始就是用非递归写的），然后用递归写了一下，一下就A掉了，简直醉了。

这个题目需要剪枝，其实就是深度优先搜索（DFS）的奇偶剪枝那篇文章的例题，如果想看递归实现和剪枝优化，请左转那篇之前写的文章，下面只说非递归实现。代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <math.h>

using namespace std;

char map_[10][10];
bool bj[10][10];
int chx[] = {0,1,0,-1};
int chy[] = {1,0,-1,0};

struct Stack
{
    int x,y,t;
    int n;
} s[100000];
int main()
{
    int n,m,tim;

    while(cin >> n >> m >> tim,n)
    {
        for(int i = 0; i < n; i++)
        {
            cin >> map_[i];
        }

        int x = -1,y = -1;
        int fx = -1,fy = -1;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(map_[i][j] == 'S')
                {
                    x = i;
                    y = j;
                }
                if(map_[i][j] == 'D')
                {
                    fx = i;
                    fy = j;
                }
            }
        }

        if(x == -1 || fx == -1)
        {
            cout << "NO" << endl;
            continue;
        }

        memset(bj,0,sizeof(bj));

        int t = 0;
        s[t].x = x;
        s[t].y = y;
        s[t].t = 0;
        s[t].n = 0;
        t++;
        bj[x][y] = 1;

        bool flag = 1;
        Stack tmp,now;
        while(t > 0)
        {
            now = s[t - 1];

            if(now.x == fx && now.y == fy)
            {
                if(now.t == tim)
                {
                    cout << "YES" << endl;
                    flag = 0;
                    break;
                }
            }

            int pdtmp = tim - now.t - fabs(fx - now.x) - fabs(fy - now.y);
            if(pdtmp < 0 || pdtmp % 2)
            {
                t--;
                if(t == 0)
                    break;
                s[t - 1].n++;
                bj[s[t].x][s[t].y] = 0;
                continue;
            }

            int tf = 0;
            for(int i = now.n; i < 4; i++)
            {
                tmp.x = now.x + chx[i];
                tmp.y = now.y + chy[i];
                tmp.t = now.t + 1;
                tmp.n = 0;
                now.n = i;

                if(tmp.x >= 0 && tmp.y >= 0 && tmp.x < n && tmp.y < m)
                {
                    if(map_[tmp.x][tmp.y] != 'X')
                    {
                        if(bj[tmp.x][tmp.y] == 0)
                        {
                            bj[tmp.x][tmp.y] = 1;

                            s[t++] = tmp;
                            tf = 1;
                            break;
                        }
                    }
                }

            }

            if(!tf)
            {
                t--;
                if(t == 0)
                    break;
                s[t - 1].n++;
                bj[s[t].x][s[t].y] = 0;
            }
            
        }

        if(flag)
            cout << "NO" <<endl;
    }
    return 0;
}

看栈结构体，除了常规的x，y，t之外，还有个n变量，他就是用来保存他的下一步遍历方向，然后在回退的时候注意不再走之前走过的路。因为回退的时候会清标记，所以如果能走之前走过的路，将会进入死循环。

也就是这个原因，在回退的时候不仅需要注意吐栈顶，还有注意更改之前元素的方向，已经清楚退出元素的标记，所以在继续遍历的时候一定要避开。

2015-02-12

最后，啸爷终于给我了他写的手写递归栈，居然过了。。。。研究一个下午也不明白他是怎么过的，算了以后就这么写吧。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <stack>
#include <map>

#pragma comment(linker, "/STACK:1024000000")
#define EPS (1e-8)
#define LL long long
#define ULL unsigned long long
#define _LL __int64
#define INF 0x3f3f3f3f
#define Mod 100007

using namespace std;

int jx[] = {-1, 0, 1, 0};
int jy[] = { 0,-1, 0, 1};

bool vis[10][10];

char Map[10][10];

struct N
{
    int x,y,c,dir;
}st[55*10*10],f,t;

bool Judge(int x,int y,int n,int m)
{
    return (1 <= x && x <= n && 1 <= y && y <= m && Map[x][y] != 'X');
}

int main()
{
    int i,j,n,m,k;

    while(scanf("%d %d %d",&n,&m,&k) && (n||m||k))
    {
        for(i = 1;i <= n; ++i)
            scanf("%s",Map[i]+1);

        int sx = -1,sy = -1,ex = -1,ey = -1;

        for(i = 1;i <= n; ++i)
        {
            for(j = 1;j <= m; ++j)
                if(Map[i][j] == 'S')
                    sx = i,sy = j;
                else if(Map[i][j] == 'D')
                    ex = i,ey = j;
        }

        if(sx == -1 || ex == -1 || (abs(ex-sx) + abs(ey-sy))%2 != k%2 )
        {
            puts("NO");
            continue;
        }

        memset(vis,false,sizeof(vis));

        vis[sx][sy] = true;
        st[0] = (N){sx,sy,0,-1};
        int Top = 0,site;

        while(Top > -1)
        {
            f = st[Top];
            site = Top;

            if(Map[f.x][f.y] == 'D' && f.c == k)
                break;

            if(f.dir == 3 || f.c > k)
            {
                Top--;
                vis[f.x][f.y] = false;
                continue;
            }

            st[site].dir = ++f.dir;

            t.x = jx[f.dir] + f.x;
            t.y = jy[f.dir] + f.y;
            t.c = f.c + 1;
            t.dir = -1;

            if(Judge(t.x,t.y,n,m) == false || vis[t.x][t.y])
                continue;

            vis[t.x][t.y] = true;

            st[++Top] = t;
        }

        if(Top > -1)
            puts("YES");
        else
            puts("NO");

    }


    return 0;
}