SWUST OJ1： 卫星照片

题目描述

农民约翰购买了他农场的W x H像素的卫星照片（1 <= W <= 80，1 <= H <= 1000），并希望确定最大的"连续"（连接）牧场。当牧场中的任何一对像素可以通过遍历作为牧场一部分的相邻垂直或水平像素来连接时，牧场是连续的。（很容易创建形状非常奇怪的牧场，甚至是围绕其他圆圈的圆圈。
每张照片都经过数字增强，将牧场区域显示为星号（'*'），将非牧场区域显示为句点（'.'）。这是一张 10 x 5 的卫星照片样本：
..**.....

.*...*....
...*** ..
这张照片显示了三个连续的牧场，分别为4，16和6像素。帮助FJ在他的每张卫星照片中找到最大的连续牧场。

输入

* Line 1: Two space-separated integers: W and H
* Lines 2..H+1: Each line contains W "*" or "." characters representing one raster line of a satellite photograph.

输出

* Line 1: The size of the largest contiguous field in the satellite photo.

样例输入

10 5
..*.....**
.**..*****
.*...*....
..****.***
..****.***

样例输出

16

#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define MAX(x,y) (x>y?x:y)
#define MIN(x,y) (x>y?y:x)
#define M 100
int dir[][2] = { {1,0},{0,-1},{0,1},{-1,0} };
char a[M][M];
int vis[M][M];
int m, n;
int max;
int num;
struct node
{int x;int y;
}q[M];
void bfs(int x0, int y0)
{int x, y, step;int head = 1, tail = 1;num = 1;vis[x0][y0] = 1;q[tail].x = x0;q[tail].y = y0;tail++;while (head < tail){x = q[head].x;y = q[head].y;for (int i = 0; i < 4; i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == '*' && vis[nx][ny] == 0){num++;vis[nx][ny] = 1;a[nx][ny] = '.';q[tail].x = nx;q[tail].y = ny;tail++;}}head++;}max = MAX(num, max);
}
int main()
{scanf("%d%d", &m, &n);for (int i = 0; i < n; i++){scanf("%s", a[i]);}for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if (a[i][j] == '*'){bfs(i, j);}}}printf("%d\n", max);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！