红与黑-阿里云开发者社区

红与黑

2017-09-03 959

简介： 红与黑总时间限制: 1000ms 内存限制: 65536kB描述有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

+关注继续查看

红与黑
总时间限制: 1000ms 内存限制: 65536kB
描述
有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上，只能向相邻的黑色瓷砖移动。请写一个程序，
计算你总共能够到达多少块黑色的瓷砖。
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H，分别表示x方向和y方向
瓷砖的数量。W和H都不超过20。在接下来的H行中，每行包括W个字符。每个字符表示
一块瓷砖的颜色，规则如下
1）‘.’：黑色的瓷砖；
2）‘#’：白色的瓷砖；
3）‘@’：黑色的瓷砖，并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时，表示输入结束。
输出
对每个数据集合，分别输出一行，显示你从初始位置出发能到达的瓷砖数(记数时包括初始
位置的瓷砖)。
样例输入
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
样例输出
45

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<queue>
 4 using namespace std;
 5 
 6 struct obj
 7 {
 8     int x,y;
 9 };
10 int w,h;
11 char a[22][22];
12 queue<struct obj> q;
13 struct obj startPoint;
14 int count=0;
15 int dx[4]={-1,0,1, 0};//上右下左
16 int dy[4]={ 0,1,0,-1};
17 
18 void bfs();
19 int main()
20 {
21     int i,j;
22     freopen("data.in","r",stdin);
23     while(scanf("%d%d",&w,&h)!=EOF)
24     {
25         getchar();
26         //printf("%d %d\n",w,h);
27         if(w==0&&h==0) break;
28         for(i=0;i<h;i++)
29         {
30             for(j=0;j<w;j++)
31             {
32                 scanf("%c",&a[i][j]);
33                 //printf("%c",a[i][j]);
34                 if(a[i][j]=='@')
35                 {
36                     startPoint.x=i;
37                     startPoint.y=j;
38                 }
39             }
40             getchar();
41             //printf("\n");
42         }
43 
44         bfs();
45         printf("%d\n",count);
46     }
47     return 0;
48 }
49 void bfs()
50 {
51     struct obj temp;
52     int xx,yy;
53 
54     count=1;
55     q.push(startPoint);
56     while(!q.empty())
57     {
58         for(int i=0;i<4;i++)
59         {
60             xx=q.front().x+dx[i];
61             yy=q.front().y+dy[i];
62             if(xx>=0&&xx<h&&yy>=0&&yy<w&&a[xx][yy]=='.')
63             {
64                 a[xx][yy]='@';
65                 temp.x=xx;
66                 temp.y=yy;
67                 q.push(temp);
68                 count++;
69             }
70         }
71         q.pop();
72     }
73 }