一本通 1249:Lake Counting"/>
一本通 1249:Lake Counting
【题目描述】
题意:有一块N×M的土地,雨后积起了水,有水标记为‘W’,干燥为‘.’。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼?
【输入】
第一行为N,M(1≤N,M≤110)。
下面为N*M的土地示意图。
【输出】
一行,共有的水洼数。
【输入样例】
10 12 W........WW. .WWW.....WWW ....WW...WW. .........WW. .........W.. ..W......W.. .W.W.....WW. W.W.W.....W. .W.W......W. ..W.......W.【输出样例】
3#include<stdio.h> #include<queue> #include<string.h> int m, n; char c[120][120]; int num = 0; int dir[][2] = { {1,0},{1,1},{-1,-1},{-1,0},{0,1},{0,-1},{1,-1},{-1,1} }; struct node {int x;int y; }q[20000]; void bfs(int xa, int ya) {int head = 1, tail = 1;q[tail].x = xa;q[tail].y = ya;tail++;num++;while (head < tail){int x = q[head].x;int y = q[head].y;for (int i = 0; i < 8; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if (nx >= 0 && nx < m && ny >= 0 && ny < n && c[nx][ny] == 'W'){q[tail].x = nx;q[tail].y = ny;c[nx][ny] = '.';tail++;}}head++;} } int main() {scanf("%d%d", &m, &n);for (int i = 0; i < m; i++){scanf("%s", c[i]);}for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (c[i][j] == 'W'){bfs(i, j);}}}printf("%d\n", num);return 0; }
更多推荐
一本通 1249:Lake Counting
发布评论