【POJ - 1979 】Red and Black
【POJ – 1979 】Red and Black（dfs+染色）
–>Red and Black
Descriptions:
有个铺满方形瓷砖的矩形房间，每块瓷砖的颜色非红即黑。某人在一块砖上，他可以移动到相邻的四块砖上。但他只能走黑砖，不能走红砖。
敲个程序统计一下这样可以走到几块红砖上。
Input
多组测试用例。每组数组开头有两个正整数W和H；W与H分别表示 x- 与 y- 方向上瓷砖的数量。W和W均不超过20。
还有H行数据，每行包含W个字符。每个字符表示各色瓷砖如下。
‘.’ – 一块黑砖
‘#’ – 一块红砖
‘@’ – 一个黑砖上的人（一组数据一个人）
输入以一行两个零为结束。
Output
对于每组测试用例，输出他从起始砖出发所能抵达的瓷砖数量（包括起始砖）。
Sample Input
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0
Sample Output
45 59 6 13
题目链接：
https://vjudge.net/problem/POJ-1979
最近在写dfs之类的题，我发现，dfs之类的题配合染色非常方便，这题亦是如此
先把所有地图都标为0，起点为1，找到”.”后编号加一即可，最后输出编号
详情看代码
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 25 using namespace std; int n,m; int ans; int sx,sy;//起点横纵坐标 int vis[Maxn][Maxn];//染色计数 char mp[Maxn][Maxn];//原始地图 int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//4个方向 void dfs(int x,int y) { if(vis[x][y])//染过色了 return; vis[x][y]=++ans;//没染色，给他染色 for(int i=0; i<4; i++)//四个方向 { int tx=x+dt[i][0]; int ty=y+dt[i][1]; if(mp[tx][ty]=='.')//满足条件 dfs(tx,ty); } } int main() { while(cin>>n>>m,n+m) { ans=0;//初始化 MEM(vis,0); MEM(mp,'#'); for(int i=0; i<m; i++)//输入地图，找到起点 for(int j=0; j<n; j++) { cin>>mp[i][j]; if(mp[i][j]=='@') sx=i,sy=j; } dfs(sx,sy); cout<<ans<<endl; } }
版权声明：本文为sky-stars原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。