美文网首页
HDU1198(DFS算法)

HDU1198(DFS算法)

作者: Alan66 | 来源:发表于2017-05-17 22:13 被阅读0次

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

    #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;
    }
    

    相关文章

      网友评论

          本文标题:HDU1198(DFS算法)

          本文链接:https://www.haomeiwen.com/subject/qkjjxxtx.html