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

HDU1241 DFS

2013年08月19日 ⁄ 综合 ⁄ 共 794字 ⁄ 字号 评论关闭
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node
{
    int x,y;
}node;
int maps[105][105];
int status[105][105];
node oil[10005];
int n,k,total;
int dir_v[8]={-1,-1,-1,0,0,1,1,1};
int dir_l[8]={-1,0,1,-1,1,-1,0,1};
void dfs(int i,int j)
{
    int h;
    int ti,tj;
    status[i][j]=1;
    for(h=0;h<8;h++)
    {
        ti= i+dir_v[h]; tj=j+dir_l[h];
        if(ti>=1&&ti<=n&&tj>=1&&tj<=k&&maps[ti][tj]&&!status[ti][tj])
            dfs(ti,tj);
    }
}
int main()
{
    int i,j,count,h;
    char ch;
    while(scanf("%d%d",&n,&k)&&(n||k))
    {
        scanf("\n");count=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=k;j++)
            {
                scanf("%c",&ch);
                if(ch=='*')maps[i][j]=0;
                else if(ch=='@')
                {
                    maps[i][j]=1;
                    oil[count].x=i;oil[count].y=j;
                    count++;
                }
            }
            if(i!=n)
                scanf("\n");
        }
        memset(status,0,sizeof(status));

        total=0;
        for(h=0;h<count;h++)
        {
            if(!status[oil[h].x][oil[h].y])
            {
                total +=1;
                dfs(oil[h].x,oil[h].y);
            }
        }
        printf("%d\n",total);
    }
    return 0;
}

抱歉!评论已关闭.