首页 > 代码库 > codevs——T2806 红与黑
codevs——T2806 红与黑
http://codevs.cn/problem/2806/
时间限制: 1 s
空间限制: 64000 KB
题目等级 : 白银 Silver
题目描述 Description
有一个矩形房间，覆盖正方形瓷砖。每块瓷砖涂成了红色或黑色。一名男子站在黑色的瓷砖上，由此出发，可以移到四个相邻瓷砖之一，但他不能移动到红砖上，只能移动到黑砖上。编写一个程序，计算他通过重复上述移动所能经过的黑砖数。
输入描述 Input Description
输入包含多个数据集。一个数据集开头行包含两个正整数W和H，W和H分别表示矩形房间的列数和行数，且都不超过20.
每个数据集有H行，其中每行包含W个字符。每个字符的含义如下所示：
‘.‘——黑砖
‘#‘——红砖
‘@‘——男子（每个数据集仅出现一次）
两个0表示输入结束。
输出描述 Output Description
对每个数据集，程序应该输出一行，包含男子从初始瓷砖出发可到达的瓷砖数。
样例输入 Sample Input
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
11 9
.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........
11 6
..#..#..#..
..#..#..#..
..#..#..###
..#..#..#@.
..#..#..#..
..#..#..#..
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0
样例输出 Sample Output
45
59
6
13
水题~
1 #include <cstring> 2 #include <cstdio> 3 4 using namespace std; 5 6 int m,n,if_break; 7 char map[25][25]; 8 9 int fx[4]={0,1,-1,0};10 int fy[4]={1,0,0,-1};11 int ans;12 void DFS(int x,int y)13 { 14 for(int i=0;i<4;i++)15 {16 int tox=x+fx[i],toy=y+fy[i];17 if(map[tox][toy]==‘#‘||map[tox][toy]==‘@‘) continue;18 if(tox<0||toy<0||tox>=n||toy>=m) continue;19 ans++;map[tox][toy]=‘#‘;20 DFS(tox,toy); 21 }22 }23 24 int main()25 {26 while(scanf("%d%d",&m,&n)&&n&&m)27 {28 for(int i=0;i<n;i++)29 scanf("%s",map[i]);30 for(int i=0;i<n;i++)31 for(int j=0;j<m;j++)32 {33 if(map[i][j]==‘@‘)34 { 35 DFS(i,j);36 printf("%d\n",ans+1);37 if_break=1; break;38 }39 if(if_break) break;40 }41 ans=if_break=0; 42 }43 return 0;44 }
1 #include <cstring> 2 #include <cstdio> 3 #include <queue> 4 5 using namespace std; 6 7 int m,n,if_break; 8 char map[25][25]; 9 10 int fx[4]={0,1,-1,0};11 int fy[4]={1,0,0,-1};12 int inq[2333][2333];13 queue<int>qx;14 queue<int>qy;15 int BFS(int x,int y)16 {17 int tox,toy,ret=1;18 qx.push(x);qy.push(y);19 inq[x][y]=1;20 while(!qx.empty()&&!qy.empty())21 {22 x=qx.front();qx.pop();23 y=qy.front();qy.pop();24 for(int i=0;i<4;i++)25 {26 tox=fx[i]+x;toy=y+fy[i];27 if(map[tox][toy]==‘#‘||inq[tox][toy]) continue;28 if(tox<0||toy<0||tox>=n||toy>=m) continue;29 ret++; inq[tox][toy]=1;30 qx.push(tox);qy.push(toy);31 }32 }33 return ret;34 }35 36 int main()37 {38 while(scanf("%d%d",&m,&n)&&n&&m)39 {40 memset(inq,0,sizeof(inq));41 for(int i=0;i<n;i++)42 scanf("%s",map[i]);43 for(int i=0;i<n;i++)44 for(int j=0;j<m;j++)45 {46 if(map[i][j]==‘@‘)47 { 48 printf("%d\n",BFS(i,j));49 if_break=1; break;50 }51 if(if_break) break;52 }53 if_break=0; 54 }55 return 0;56 }
codevs——T2806 红与黑
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。