给一个m*n的矩阵，数字是0或是1，统计其中八连块的个数，和《算法竞赛入门经典》6.4.1黑白图像一样，应该是那个的原型吧。
代码如下：
View Code 1 #include2 #include 3 4 const int maxn = 105; 5 int mat[maxn][maxn], vis[maxn][maxn]; 6 7 void dfs(int x, int y) 8 { 9 if(vis[x][y] || !mat[x][y]) return;10 vis[x][y] = 1;11 dfs(x-1, y-1); dfs(x-1, y); dfs(x-1, y+1);12 dfs(x, y-1); dfs(x, y+1);13 dfs(x+1, y-1); dfs(x+1, y); dfs(x+1, y+1);14 }15 16 int main()17 {18 #ifdef LOCAL19 freopen("in", "r", stdin);20 #endif21 int m, n;22 while(scanf("%d%d", &m , &n) != EOF && m)23 {24 char s[maxn];25 memset(mat, 0, sizeof(mat));26 memset(vis, 0, sizeof(vis));27 for(int i = 0; i < m; i++)28 {29 scanf("%s", s);30 for(int j = 0; j < n; j++)31 {32 if(s[j] == '*') mat[i+1][j+1] = 0;33 else if(s[j] == '@') mat[i+1][j+1] = 1;34 }35 }36 int cnt = 0;37 for(int i = 1; i <= m; i++)38 for(int j = 1; j <= n; j++)39 if(!vis[i][j] && mat[i][j])40 {41 cnt++;42 dfs(i, j);43 }44 printf("%d\n", cnt);45 }46 return 0;47 }
上面是用递归的方式实现的，也可用显式栈来代替递归，代码如下：
View Code 1 #include2 #include 3 #include 4 using namespace std; 5 6 const int maxn = 105; 7 int mat[maxn][maxn], vis[maxn][maxn]; 8 int m, n; 9 10 const int dir[][2] = { { 1, 1}, { 1, 0}, { 1, -1}, { 0, 1}, { 0, -1}, {-1, 1}, {-1, 0}, {-1,-1} };11 12 struct Pos13 {14 int x, y;15 };16 17 void dfs(int x, int y)18 {19 stack s;20 Pos t;21 t.x = x;22 t.y = y;23 s.push(t);24 while(!s.empty())25 {26 t = s.top();27 s.pop();28 int x = t.x, y = t.y;29 for(int i = 0; i < 8; i++)30 {31 int nx, ny;32 nx = x + dir[i][0];33 ny = y + dir[i][1];34 if(nx >= 0 && nx < m && ny >= 0 && ny < n)35 if(mat[nx][ny] && !vis[nx][ny])36 {37 t.x = nx;38 t.y = ny;39 s.push(t);40 vis[nx][ny] = 1;41 }42 }43 }44 }45 46 47 int main()48 {49 #ifdef LOCAL50 freopen("in", "r", stdin);51 #endif52 while(scanf("%d%d", &m, &n) != EOF && m)53 {54 char s[maxn];55 memset(mat, 0, sizeof(mat));56 memset(vis, 0, sizeof(vis));57 for(int i = 0; i < m; i++)58 {59 scanf("%s", s);60 for(int j = 0; j < n; j++)61 if(s[j] == '@') mat[i][j] = 1;62 }63 int cnt = 0;64 for(int i = 0; i < m; i++)65 for(int j = 0; j < n; j++)66 if(!vis[i][j] && mat[i][j])67 {68 cnt++;69 dfs(i, j);70 }71 printf("%d\n", cnt);72 }73 return 0;74 }