题目链接:http://poj.org/problem?id=1562 还是广搜比较好写啊……
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 #include <queue> 8 using namespace std; 9 int n, m, f[110][110]; 10 char map[110][110]; 11 struct nod{ 12 int x, y; 13 }; 14 queue<nod> Q; 15 const int dir[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}}; 16 bool inMap(int x, int y){ 17 return x >= 0 && x < n && y >= 0 && y < m; 18 } 19 void bfs(int sx, int sy, int k){ 20 f[sx][sy] = k; 21 nod S; 22 S.x = sx; S.y = sy; 23 Q.push(S); 24 while (!Q.empty()){ 25 nod u = Q.front(); 26 int x = u.x, y = u.y; 27 Q.pop(); 28 for (int i = 0; i < 8; i++){ 29 int xx = x + dir[i][0]; 30 int yy = y + dir[i][1]; 31 if (!inMap(xx, yy) || map[xx][yy] == '*') continue; 32 if (!f[xx][yy]){ 33 f[xx][yy] = k; 34 nod v; 35 v.x = xx; v.y = yy; 36 Q.push(v); 37 } 38 } 39 } 40 } 41 int main(){ 42 while (~scanf("%d%d", &n, &m)){ 43 if (!m && !n) break; 44 for (int i = 0; i < n; i++) scanf("%s", map[i]); 45 memset(f, 0, sizeof(f)); 46 int k = 1; 47 for (int i = 0; i < n; i++) 48 for (int j = 0; j < m; j++) 49 if (map[i][j] == '@' && !f[i][j]) bfs(i, j, k++); 50 int ans = 0; 51 for (int i = 0; i < n; i++) 52 for (int j = 0; j < m; j++) 53 ans = max(ans, f[i][j]); 54 printf("%d\n", ans); 55 } 56 return 0; 57
|