hud 1312 搜索

http://acm.hdu.edu.cn/showproblem.php?pid=1312

方法一：广度优先搜索。

利用队列“先进先出FIFO”的特点（本例用数组queue和标记L等效一个队列），距离起点越近越先被搜索，适合计算消费与距离成比例的问题。

#include<stdio.h>
#define N 22
int flag[N][N],W,H,count,L,i,j;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
struct node
{
    int x,y;
}next,queue[N*N];
void BFS(int x,int y)
{
    queue[0].x=x;
    queue[0].y=y;
    count++;L++;
    for(i=0;i<L;i++)
    {
        for(j=0;j<4;j++)
        {
            next.x=queue[i].x+dir[j][0];
            next.y=queue[i].y+dir[j][1];
            if(flag[next.x][next.y]==0&&next.x>=0&&next.x<W&&next.y>=0&&next.y<H)
            {
                count++;
                flag[next.x][next.y]=1;
                queue[L].x=next.x;
                queue[L++].y=next.y;
            }
        }
    }
}
int main()
{
    int x,y;
    char t;
    while(scanf("%d%d",&W,&H),W||H)
    {
        count=0;L=0;
        for(i=0;i<H;i++)
        {
            getchar();
            for(j=0;j<W;j++)
            {
                scanf("%c",&t);
                if(t=='.')
                    flag[j][i]=0;
                if(t=='#')
                    flag[j][i]=1;
                if(t=='@)
                {
                    x=j;
                    y=i;
                    flag[j][i]=1;
                }
            }
        }
        BFS(x,y);
        printf("%d\n",count);
    }
    return 0;
}

方法二：深度优先搜索。

通过递归调用系统栈，利用栈“先进后出FILO”的特点，对一个方向搜索到底后逐步向上回溯。

#include<stdio.h>
#define N 25
int flag[N][N],count,W,H;
int dir[4][2]={1,0, 0,1, -1,0, 0,-1};
void DFS(int x,int y)
{
    int next_x,next_y,i;
    for(i=0;i<4;i++)
    {
        next_x=x+dir[i][0];
        next_y=y+dir[i][1];
        flag[y][x]=1;
        if(flag[next_y][next_x]==0&&next_x>=0&&next_x<W&&next_y>=0&&next_y<H)
        {
            count++;
            DFS(next_x,next_y);
        }
    }
}
int main()
{
    int i,j,x,y;
    char t;
    while(scanf("%d%d",&W,&H),W||H)
    {
        for(i=0;i<H;i++)
        {
            getchar();
            for(j=0;j<W;j++)
            {
                scanf("%c",&t);
                if(t=='.')
                    flag[i][j]=0;
                if(t=='#')
                    flag[i][j]=1;
                if(t=='@)
                {
                    x=j;
                    y=i;
                    count=1;             //注意count初始化一定不要放在dfs函数中，否则递归调用时会不停初始化
                }
            }
        }
        DFS(x,y);
        printf("%d\n",count);
    }
    return 0;
}