DFS模板

（UVA572）
简单的DFS模板题

#include<cstdio>
#include<cstring>

char grid[101][101];
int m,n;
int dir[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};

void dfs(int x,int y)
{
    int i,xx,yy;
    grid[x][y]='*';
    for(i=0;i<8;i++)
    {
        xx=x+dir[i][0];
        yy=y+dir[i][1];
        if(xx<0||yy<0||xx>=m||yy>=n) continue;
        if(grid[xx][yy]=='@')
            dfs(xx,yy);
    }
}

int main()
{
    int i,j;
    int count;
    while(1)
    {
        scanf("%d%d",&m,&n);
        if(m==0) break;
        for(i=0;i<m;i++)
            scanf("%s",grid[i]);
        count=0;
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                if(grid[i][j]=='@')
        {
            dfs(i,j);
            count++;
        }
        printf("%d\n",count);
    }
    return 0;
}

ZOJ2110/HDU1010
稍微复杂一点的模板，编译器用G++，用C++会CE

#include<cstdio>
#include<cstring>
#include<cmath>
int n,m,t;
char mamp[9][9];
int di,dj;
bool escape;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//分别表示上下左右四个方向

void dfs(int si,int sj,int cnt)
{
    int i,temp;
    if(si>n||sj>m||si<=0||sj<=0)
        return;
    if(si==di&&sj==dj&&cnt==t)
    {
        escape=1;
        return;
    }
    temp=(t-cnt)-fabs(si-di)-fabs(sj-dj);   //fabs是求绝对值的函数,头文件在math.h中
    if(temp<0||temp%2) return;
    for(i=0;i<4;i++)
    {
        if(mamp[si+dir[i][0]][sj+dir[i][1]]!='X')
        {
            mamp[si+dir[i][0]][sj+dir[i][1]]='X';
            dfs(si+dir[i][0],sj+dir[i][1],cnt+1);
            if(escape) return;
            mamp[si+dir[i][0]][sj+dir[i][1]]='.';
        }
    }
    return;
}
int main()
{
    int i,j;
    int si,sj;
    while(scanf("%d%d%d",&n,&m,&t)==3&&n&&m&&t)
    {
       int wall=0;
       char temp;
       scanf("%c",&temp);
       for(i=1;i<=n;i++)
       {
           for(j=1;j<=m;j++)
           {
               scanf("%c",&mamp[i][j]);
               if(mamp[i][j]=='S')
               {
                   si=i;
                   sj=j;
               }
               else if(mamp[i][j]=='D')
               {
                   di=i;
                   dj=j;
               }
               else if(mamp[i][j]=='X')
                    wall++;
           }
           scanf("%c",&temp);
       }
       if(n*m-wall<=t)
       {
           printf("NO\n");
           continue;
       }
       escape=0;
       mamp[si][sj]='X';
       dfs(si,sj,0);
       if(escape) printf("YES\n");
       else printf("NO\n");
    }
    return 0;
}