E - Red and Black

本是古典何须时尚 2022-03-20 08:07 145阅读 0赞

### 题目描述： ###

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.  
Input  
The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.

There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.

‘.’ - a black tile  
‘\#’ - a red tile  
‘@’ - a man on a black tile(appears exactly once in a data set)  
Output  
For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).  
Sample Input  
6 9  
…\#.  
…\#  
…  
…  
…  
…  
…  
\#@…\#  
.\#…\#.  
11 9  
.\#…  
.\#.\#\#\#\#\#\#\#.  
.\#.\#…\#.  
.\#.\#.\#\#\#.\#.  
.\#.\#…@\#.\#.  
.\#.\#\#\#\#\#.\#.  
.\#…\#.  
.\#\#\#\#\#\#\#\#\#.  
…  
11 6  
…\#…\#…\#…  
…\#…\#…\#…  
…\#…\#…\#\#\#  
…\#…\#…\#@.  
…\#…\#…\#…  
…\#…\#…\#…  
7 7  
…\#.\#…  
…\#.\#…  
\#\#\#.\#\#\#  
…@…  
\#\#\#.\#\#\#  
…\#.\#…  
…\#.\#…  
0 0  
Sample Output  
45  
59  
6  
13  
题意：@人被困在迷宫里，求他最多能走多少步。\#是墙。  
分析：这个题bfs和dfs都可以。为了避免重复走，可以将走过的路标记为墙

#include"stdio.h"
    #include"string.h"
    typedef struct
    {
        int x,y;
    }Local;
    Local local[10000];
    char Map[20][20];
    int n,k;
    int cont;
    void bfs(int x,int y)
    {
        Local T;
        local[0].x=x;local[0].y=y;
        int i=0,j=1;
        while(i<j)
        {
            T=local[i];
            T.x=local[i].x-1;
            if(T.x>=0&&Map[T.x][T.y]=='.')
            {
                local[j++]=T;
                Map[T.x][T.y]='#';
            }
            T=local[i];
            T.x++;
            if(T.x<k&&Map[T.x][T.y]=='.')
            {
                local[j++]=T;
                Map[T.x][T.y]='#';//标记为墙
            }
            T=local[i];
            T.y--;
            if(T.y>=0&&Map[T.x][T.y]=='.')
            {
                local[j++]=T;
                Map[T.x][T.y]='#';
            }
            T=local[i];
            T.y++;
            if(T.y<n&&Map[T.x][T.y]=='.')
            {
                local[j++]=T;
                Map[T.x][T.y]='#';
            }
            i++;
        }
        cont=i;
    }
    int main()
    {
       int x,y;
        while(~scanf("%d%d",&n,&k))
        {
            if(n==0&&k==0)
                break;
            for(int i=0;i<k;i++)
                scanf("%s",Map[i]);
            for(int i=0;i<k;i++)
                for(int j=0;j<n;j++)
                   if(Map[i][j]=='@')
                      {
                          x=i;y=j;
                      }
            cont=1;
            bfs(x,y);
            printf("%d\n",cont);
        }
    }