HDU1198（DFS算法）

这个题需要注意细节，不然卡在那儿很烦，我的做法比较无脑，代码太长，但理解方便一点。

#include<cstdio>
#include<cstring>
char grid[1005][1005];
int m,n;
int dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};//分别表示上下左右四个方向
//为1表示这个方向有接口，为0表示这个方向没有接口
/*int type[11][4]={{1,1,0,0},{0,1,1,0},
                 {1,0,0,1},{0,0,1,1},
                 {0,1,0,1},{1,0,1,0},
                 {1,1,1,0},{1,1,0,1},
                 {1,0,1,1},{0,1,1,1},
                 {1,1,1,1}};
这里面可以简化下面的自己赋值，但还不会用*/
int dfs(int x,int y)
{
    if(grid[x][y]=='*')
        grid[x][y]='!';
    else
        return 0;
    for(int i=0;i<4;i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx>=0&&xx<3*m&&yy>=0&&yy<3*n)        //注意范围
            dfs(xx,yy);
    }
    return 1;
}

int main()
{
    while(scanf("%d%d",&m,&n)==2&&m!=-1&&n!=-1)
    {
        memset(grid,0,sizeof(grid));
        int cunt=0;
        char cnt;
        for(int i=0;i<m;i++)
        {
            getchar();
            for(int j=0;j<n;j++)
          {
            scanf("%c",&cnt);
            if(cnt=='A')
            {
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3]='*';
            }
            if(cnt=='B')
            {
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
            }
           if(cnt=='C')
           {
                grid[i*3+2][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3]='*';
           }
           if(cnt=='D')
           {
                grid[i*3+2][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
           }
           if(cnt=='E')
           {
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+2][j*3+1]='*';
           }
           if(cnt=='F')
           {
                grid[i*3+1][j*3]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
           }
           if(cnt=='G')
           {
                grid[i*3+1][j*3]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
                grid[i*3][j*3+1]='*';
           }
           if(cnt=='H')
           {
                grid[i*3+2][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3]='*';
           }
           if(cnt=='I')
           {
                grid[i*3+1][j*3]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
                grid[i*3+2][j*3+1]='*';
           }
           if(cnt=='J')
           {
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
                grid[i*3+2][j*3+1]='*';
           }
           if(cnt=='K')
           {
                grid[i*3][j*3+1]='*';
                grid[i*3+1][j*3]='*';
                grid[i*3+1][j*3+1]='*';
                grid[i*3+1][j*3+2]='*';
                grid[i*3+2][j*3+1]='*';
           }
        }
        }
        for(int i=0;i<m*3;i++)          //注意循环的范围
            for(int j=0;j<n*3;j++)
                if(dfs(i,j))            //先进入DFS算法再判断是否可行
                    ++cunt;
        printf("%d\n",cunt);
    }
    return 0;
}