hdu 1312Red and Black

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

题意：就是找从@出发的能经过的'.'的数目。

dfs写法：

View Code

#include<stdio.h>
#include<string.h>
int col,row;
int sx,sy;
int sum;
int vis[25][25];
char map[25][25];
void dfs(int x,int y)
{
    if(vis[x-1][y]==0&&map[x-1][y]=='.') 
    {
        sum++;
        vis[x-1][y]=1;
        dfs(x-1,y);
    }
    if(vis[x][y+1]==0&&map[x][y+1]=='.') 
    {
        sum++;
        vis[x][y+1]=1;
        dfs(x,y+1);
    }
    if(vis[x+1][y]==0&&map[x+1][y]=='.') 
    {
        sum++;
        vis[x+1][y]=1;
        dfs(x+1,y);
    }
    if(vis[x][y-1]==0&&map[x][y-1]=='.') 
    {
        sum++;
        vis[x][y-1]=1;
        dfs(x,y-1);
    }
}
int main()
{
    int i;
    int j;
    while(~scanf("%d%d",&col,&row)&&(col||row))
    {
        sum=0;
        memset(map,'#',sizeof(map));
        memset(vis,0,sizeof(vis));
        for(i=0;i<row;i++)
        scanf("%s",map[i]);
        for(i=0;i<row;i++)
        {
            for(j=0;j<col;j++)
            {
                if(map[i][j]=='@')
                {
                    sx=i;
                sy=j;
                vis[sx][sy]=1;
                }
            }
        }
        dfs(sx,sy);
        printf("%d\n",sum+1);
    }
}

bfs写法：

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 int vis[25][25];
 4 char map[25][25];
 5 char queue[625];
 6 int col,row;
 7 int sx,sy,sum;
 8 int front,rear;
 9 char top;
10 void bfs(int x,int y)
11 {
12     front=0;
13     rear=0;
14     vis[x][y]=1;
15     queue[rear++]=map[x][y];
16     while(front<rear)
17     {
18         top=queue[front++];
19         if(map[x-1][y]=='.'&&vis[x-1][y]==0)
20         {
21             vis[x-1][y]=1;
22             sum++;
23             bfs(x-1,y);
24         }
25         if(map[x][y+1]=='.'&&vis[x][y+1]==0)
26         {
27             vis[x][y+1]=1;
28             sum++;
29             bfs(x,y+1);
30         }
31         if(map[x+1][y]=='.'&&vis[x+1][y]==0)
32         {
33             vis[x+1][y]=1;
34             sum++;
35             bfs(x+1,y);
36         }
37         if(map[x][y-1]=='.'&&vis[x][y-1]==0)
38         {
39             vis[x][y-1]=1;
40             sum++;
41             bfs(x,y-1);
42         }
43     }
44 }
45 int main()
46 {
47     int i,j;
48     while(~scanf("%d%d",&col,&row)&&(col||row))
49     {
50         sum=0;
51         memset(vis,0,sizeof(vis));
52         memset(map,'#',sizeof(map));
53         for(i=0;i<row;i++)
54         {
55             scanf("%s",map[i]);
56         }
57         for(i=0;i<row;i++)
58         {
59             for(j=0;j<col;j++)
60             {
61                 if(map[i][j]=='@')
62                 {
63                     sx=i;
64                     sy=j;
65                     vis[i][j]=1;
66                 }
67             }
68         }
69         bfs(sx,sy);
70         printf("%d\n",sum+1);
71     }
72 }