现在的位置: 首页 > 综合 > 正文

zoj 2412 dfs

2012年12月23日 ⁄ 综合 ⁄ 共 1162字 ⁄ 字号 评论关闭
#include<stdio.h>
char jk[55][55];
int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
int flag[55][55];
int m,n;
void dfs(int x,int y)
{                   //注意这里比较蛋疼,m,n刚好和x,y坐标是相反的。 规律是所在的点和接下来要搜索的点必须相接才行。
    flag[x][y]=1;
    if(x!=0&&jk[x-1][y]!='A'&&jk[x-1][y]!='B'&&jk[x-1][y]!='F'&&jk[x-1][y]!='G'&&flag[x-1][y]!=1
        &&jk[x][y]!='C'&&jk[x][y]!='D'&&jk[x][y]!='F'&&jk[x][y]!='I')
         dfs(x-1,y);
     if(x!=m-1&&jk[x+1][y]!='C'&&jk[x+1][y]!='D'&&jk[x+1][y]!='F'&&jk[x+1][y]!='I'&&flag[x+1][y]!=1
        &&jk[x][y]!='A'&&jk[x][y]!='B'&&jk[x][y]!='F'&&jk[x][y]!='G')
         dfs(x+1,y);
     if(y!=n-1&&jk[x][y+1]!='B'&&jk[x][y+1]!='D'&&jk[x][y+1]!='E'&&jk[x][y+1]!='J'&&flag[x][y+1]!=1
        &&jk[x][y]!='A'&&jk[x][y]!='C'&&jk[x][y]!='E'&&jk[x][y]!='H')
         dfs(x,y+1);
     if(y!=0&&jk[x][y-1]!='C'&&jk[x][y-1]!='A'&&jk[x][y-1]!='E'&&jk[x][y-1]!='H'&&flag[x][y-1]!=1
        &&jk[x][y]!='B'&&jk[x][y]!='D'&&jk[x][y]!='E'&&jk[x][y]!='J')
         dfs(x,y-1);
    return ;
}
int main()
{
    //freopen("input.txt","r",stdin);
    int num,i,j;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(m<0||n<0)
            break;
        num=0;
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
            {
                scanf(" %c",&jk[i][j]);  //    for(i=0;i<n;i++)     scanf("%s",jk[i]);
                flag[i][j]=0;
            }
        for(i=0; i<m; i++)
            for(j=0; j<n; j++)
            {
                if(flag[i][j]==0)
                {
                    num++;
                    dfs(i,j);
                }
            }
        printf("%d\n",num);
    }
    return 0;
}




抱歉!评论已关闭.