Red and Black (找到一个标记一个)
题目链接：http://poj.org/problem?id=1979
题目大意：
有一个长方形的房间，上面铺着正方形的瓷砖。每块瓷砖都是红色或黑色的。一个男人站在一块黑色的瓷砖上。从一个瓦片，他可以移动到四个相邻瓦片中的一个。但是他不能在红瓦上移动，他只能在黑瓦上移动。
编写一个程序，通过重复上面描述的动作来计算他可以到达的黑色方块的数量。
输入
输入由多个数据集组成。数据集以包含两个正整数W和H的行开始;W和H分别是x和y方向上的瓦片数。W和H不超过20。
'.——一块黑瓷砖
“#”——红色瓷砖
@——一个男人在黑色的平铺上(数据集中只出现一次）
思路：
找到起始位置然后进行 dfs，找到一个就标记一个，然后一直走下去
一开始自己想错了，我以为是找最多的可以走的。但是后来感觉根据题目的意思来看就是找到一条路就可以了。哭泣
AC代码：
1 #include <cstdio> 2 #include <string> 3 #include <iostream> 4 #include <algorithm> 5 #include <string.h> 6 #include <math.h> 7 #include <vector> 8 9 using namespace std; 10 11 const int maxn = 30; 12 13 char ss[maxn][maxn]; 14 int mx[] = {0,0,1,-1}; 15 int my[] = {1,-1,0,0}; 16 int vis[maxn][maxn]; 17 int n,m; 18 int cnt = 0; 19 20 bool check(int i,int j) 21 { 22 if (ss[i][j] == '.' && !vis[i][j]) 23 return true; 24 return false; 25 } 26 27 void dfs(int row,int col) 28 { 29 for (int i=0;i<4;i++) 30 { 31 int nx = row + mx[i]; 32 int ny = col + my[i]; 33 if (check(nx,ny)) 34 { 35 cnt++; 36 vis[nx][ny] = 1; 37 dfs(nx,ny); 38 } 39 } 40 41 } 42 43 44 int main() { 45 while (cin >> m >> n) { 46 if (m == 0 && n == 0) 47 return 0; 48 bool flag = false; 49 cnt = 0; 50 memset(vis,0, sizeof(vis)); 51 memset(ss,'#', sizeof(ss)); 52 for (int i = 1; i <= n; i++) { 53 for (int j = 1; j <= m; j++) { 54 cin >> ss[i][j]; 55 } 56 } 57 for (int i = 1; i <= n; i++) { 58 for (int j = 1; j <= m; j++) { 59 if (ss[i][j] == '@') { 60 dfs(i, j); 61 printf("%d\n", cnt + 1); 62 flag = true; 63 break; 64 } 65 } 66 if (flag) 67 break; 68 } 69 } 70 }
投递锐捷网络股份有限公司等公司7个岗位 >