研究地球空间科学的永强想研究海岸线的长度和海岸线面积之间的关系，为此他找来了很多航拍图像。在航拍图像上利用图像分割的方法，把图像的每个像素标记成陆地（1）和水面（0）。
已知每张图最底部的一条边都是陆地，并且在一张图上陆地都是四邻域联通的。
第一行为两个整数m和n，
接下来m行每行会有n个数，0表示水面，1表示陆地。
去噪后陆地部分的面积。
5 6 1 0 0 1 0 0 0 0 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1
21
//用递归会导致java栈不够用而报错，改为非递归方式 import java.util.*;
class Node{
int x;
int y;
public Node(int x,int y){
this.x=x;
this.y=y;
}
}
public class Main{
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int m = in.nextInt();
int n = in.nextInt();
int[][] map = new int[m][n];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
map[i][j] = in.nextInt();
}
}
int count=0;
for(int j = 0; j < n; j++){
count+=dfs(map,0,j,0,-1);
}
for(int i = 0; i < m; i++){
count+=dfs(map,i,0,0,-1);
count+=dfs(map,i,n-1,0,-1);
}
int res=0;
for(int j = n-2; j>=1; j--){
for(int i = m-2; i >= 1; i--){
if(map[i][j]==0){
map[i][j]=1;
}
}
}
res=dfs(map,m-1,0,1,2);
System.out.println(res);
}
public static int dfs(int[][] map,int i,int j,int s,int t){
LinkedList<Node> list=new LinkedList<Node>();
if(map[i][j]==s){
list.addLast(new Node(i,j));
}
int count=0;
while(!list.isEmpty()){
Node tmp=list.pollLast();
i=tmp.x;
j=tmp.y;
if(map[i][j]==s){
count++;
map[i][j]=t;
}
if(j>0 && map[i][j-1]==s) {
list.addLast(new Node(i,j-1));
}
if(j<map[0].length-1 && map[i][j+1]==s)
list.addLast(new Node(i,j+1));
if(i>0 && map[i-1][j]==s)
list.addLast(new Node(i-1,j));
if(i<map.length-1 && map[i+1][j]==s)
list.addLast(new Node(i+1,j));
}
return count;
}
} 
#include <bits/stdc++.h>
using namespace std;
int result = 0;
void surround(vector<vector<int>>& pic, int i, int j) {
if (i < 0 || i >= pic.size() || j < 0 || j >= pic[0].size() || pic[i][j] == 1 || pic[i][j] == 2) return;
pic[i][j] = 2;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
surround(pic, i + dx[k], j + dy[k]);
}
}
void cal_area(vector<vector<int>>& pic, int i, int j) {
if (i < 0 || i >= pic.size() || j < 0 || j >= pic[0].size() || pic[i][j] == 2 || pic[i][j] == 3) return;
pic[i][j] = 3;
result++;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
for (int k = 0; k < 4; k++) {
cal_area(pic, i + dx[k], j + dy[k]);
}
}
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> pic(m, vector<int> (n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
cin >> pic[i][j];
}
}
// 1.从边缘且为水的位置开始遍历，将所有没有被陆地包围的水标记为2
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
bool edge = i == 0 || i == m - 1 || j == 0 || j == n - 1;
if (pic[i][j] == 0 && edge) {
surround(pic, i, j);
}
}
}
// 2.将被陆地包围的水标记为1(陆地)
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
if (pic[i][j] == 0) {
pic[i][j] = 1;
}
}
}
// 3.从下边缘且为陆地的位置开始遍历，标记所有陆地为3，同时计算面积
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++){
bool bottom = i == m - 1;
if (pic[i][j] == 1 && bottom) {
cal_area(pic, i, j);
}
}
}
cout << result << endl;
return 0;
} 
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 850
int grid[MAX_N][MAX_N];
const int dirs[] = {0, -1, 0, 1, 0};
void surround(int m, int n, int x, int y) {
*(*(grid + y) + x) = 2;
int i, nx, ny;
for (i = 0; i < 4; ++i) {
nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || nx == n || ny < 0 || ny == m || *(*(grid + ny) + nx))
continue; // 在递归之前拦截 -- 减少递归深度带来的空间负载 overhead
surround(m, n, nx, ny);
}
}
int DFS2(int m, int n, int x, int y) {
*(*(grid + y) + x) = 0; // mark as seen
int i, nx, ny, areas = 1;
for (i = 0; i < 4; ++i) {
nx = x + dirs[i], ny = y + dirs[i + 1];
if (nx < 0 || nx == n || ny < 0 || ny == m || *(*(grid + ny) + nx) != 1)
continue; // 在递归之前拦截 -- 减少递归深度带来的空间负载 overhead
areas += DFS2(m, n, nx, ny);
}
return areas;
}
void print_grid(int m, int n) {
int x, y;
for (y = 0; y < m; ++y) {
for (x = 0; x < n; ++x)
fprintf(stdout, "%d ", *(*(grid + y) + x));
fputc(10, stdout);
}
}
int main(const int argc, const char* const argv[]) {
int m, n;
fscanf(stdin, "%d %d", &m, &n);
int x, y;
for (y = 0; y < m; ++y)
for (x = 0; x < n; ++x)
scanf("%d", &grid[y][x]);
for (x = 0; x < n; ++x) {
if (grid[0][x] == 0) surround(m, n, x, 0);
if (grid[m - 1][x] == 0) surround(m, n, x, m - 1);
}
for (y = 0; y < m; ++y) {
if (grid[y][0] == 0) surround(m, n, 0, y);
if (grid[y][n - 1] == 0) surround(m, n, n - 1, y);
}
int ans = 0;
for (y = 0; y < m; ++y)
for (x = 0; x < n; ++x)
if (!*(*(grid + y) + x)) *(*(grid + y) + x) = 1;
return printf("%d\n", DFS2(m, n, 0, m - 1)), 0;
} #include<bits/stdc++.h>using namespace std;void Link(vector<vector<int>> &data,vector<pair<int,int>> &help,int value,int change){while (help.size() > 0) {pair<int, int> cur = help.back();int row = data.size();int col = data[0].size();help.pop_back();int cur_row = cur.first;int cur_col = cur.second;if (cur_row > 0 && data[cur_row - 1][cur_col] == value) {data[cur_row - 1][cur_col] = change;help.push_back(make_pair(cur_row - 1, cur_col));}if (cur_row < row-1 && data[cur_row + 1][cur_col] == value) {data[cur_row + 1][cur_col] = change;help.push_back(make_pair(cur_row + 1, cur_col));}if (cur_col > 0 && data[cur_row][cur_col - 1] == value) {data[cur_row][cur_col-1] = change;help.push_back(make_pair(cur_row, cur_col-1));}if (cur_col < col-1 && data[cur_row][cur_col+1] == value) {data[cur_row][cur_col+1] = change;help.push_back(make_pair(cur_row, cur_col + 1));}}}int main() {int row, col;cin >> row >> col;vector<vector<int>> data(row, vector<int>(col, 0));for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)cin >> data[i][j];vector<pair<int, int>> help;for (int j = 0; j < col; j++){if (data[0][j] == 0) {data[0][j] = -1;help.push_back(make_pair(0,j));}}for (int i = 1; i < row; i++){if (data[i][0] == 0) {data[i][0] = -1;help.push_back(make_pair(i, 0));}if (data[i][col-1] == 0) {data[i][col-1] = -1;help.push_back(make_pair(i, col-1));}}//水连通Link(data,help,0,-1);int res = 0;//陆地内去噪for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)if (data[i][j] == 0)data[i][j] = 1;for (int j = 0; j<col; j++)if (data[row - 1][j] == 1) {data[row - 1][j] = 2;help.push_back(make_pair(row - 1, j));}//陆地连通Link(data,help,1,2);for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (data[i][j] ==2) {res++;}}}cout << res;//system("pause");return 0;}
#include<iostream>
using namespace std;
int m,n;
int *p;
int sum;
/**让一个值为key的节点和他周围值为key的节点连通
*key!=set
*/
void link(int key,int sx,int sy,int set)
{
sum++;
p[sy*n+sx]=set;
if(sx-1>=0&&p[sy*n+sx-1]==key) link(key,sx-1,sy,set);
if(sx+1<n&&p[sy*n+sx+1]==key) link(key,sx+1,sy,set);
if(sy-1>=0&&p[(sy-1)*n+sx]==key) link(key,sx,sy-1,set);
if(sy+1<m&&p[(sy+1)*n+sx]==key) link(key,sx,sy+1,set);
}
int main()
{
int i,j;
cin>>m>>n;
p=new int[m*n];
for(i=0;i<m*n;i++)
{
cin>>p[i];
}
/*连通所有海洋且标记为-1*/
for(i=0;i<n;i++)
{
if(p[i]==0) link(0,i,0,-1);
}
for(i=0;i<m;i++)
{
if(p[i*n]==0) link(0,0,i,-1);
if(p[i*n+n-1]==0) link(0,n-1,i,-1);
}
/*其余的都为陆地，将地中海变为陆地*/
for(i=1;i<m-1;i++)
{
for(j=1;j<n-1;j++)
{
if(p[i*n+j]==0) p[i*n+j]=1;
}
}
sum=0;
/*计算陆地面积*/
link(1,0,m-1,2);
cout<<sum<<endl;
}
#只过了83%，算法复杂度较高，不知道该如何优化了，求解答！！
from _collections import deque
def bfs(maps,i,j,s,t):
q=deque()
if maps[i][j]==s:
q.append((i,j))
cnt=0
while q:
i,j=q.popleft()
cnt+=1
maps[i][j]=t
if j>0 and maps[i][j-1]==s and (i,j-1) not in q:
q.append((i,j-1))
if j<len(maps[0])-1 and maps[i][j+1]==s and (i,j+1) not in q:
q.append((i,j+1))
if i>0 and maps[i-1][j]==s and (i-1,j) not in q:
q.append((i-1,j))
if i<len(maps)-1 and maps[i+1][j]==s and (i+1,j) not in q:
q.append((i+1,j))
return cnt
m, n = [int(a) for a in input().strip().split(' ')]
grid = []
for i in range(m):
grid.append([int(a) for a in input().strip().split(' ')])
if m==1:
print(sum(grid))
#从左，上，右 三个方向将一定为水的地方置-1
#从上渗透
for j in range(n):
bfs(grid,0,j,0,-1)
# a=grid==[[1, -1, -1, 1, -1, -1], [-1, -1, 1, 0, 1, -1], [1, 1, 1, 1, 1, -1], [1, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
# print(a)
#从左，右两边渗透
for i in range(m):
bfs(grid,i,0,0,-1)
bfs(grid,i,n-1,0,-1)
# b=grid==[[1, -1, -1, 1, -1, -1], [-1, -1, 1, 0, 1, -1], [1, 1, 1, 1, 1, -1], [1, 0, 0, 1, 1, 1], [1, 1, 1, 1, 1, 1]]
# print(b)
#剩下的一定就是被陆地包围的水，可以放心的让水都为1
res=0
for j in range(n-2,0,-1):
for i in range(m-2,0,-1):
if grid[i][j]==0:
grid[i][j]=1
#再从下面渗透，如果碰到1，就置2，表示已经访问过。有的没办法渗透到的陆地，因为与底边陆地脱离，不会算在结果中
res=bfs(grid,m-1,0,1,2)
#[[1, -1, -1, 2, -1, -1], [-1, -1, 2, 2, 2, -1], [2, 2, 2, 2, 2, -1], [2, 2, 2, 2, 2, 2], [2, 2, 2, 2, 2, 2]]
# print(grid)
print(res)
## 将所有边缘上的海洋联通起来
def dfs1(i, j):
if i < 0&nbs***bsp;i >= m&nbs***bsp;j < 0&nbs***bsp;j >= n&nbs***bsp;visited[i][j] == 1:
return
grid[i][j] = -1
visited[i][j] = 1
for di, dj in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
if 0<=i+di<m and 0<=j+dj<n and grid[i+di][j+dj] != 1:
dfs1(i+di, j+dj)
## 计算非-1的区域的面积
def dfs2(i, j):
if i < 0&nbs***bsp;i >= m&nbs***bsp;j < 0&nbs***bsp;j >= n&nbs***bsp;visited[i][j] == 1:
return 0
visited[i][j] = 1
ans = 1
for di, dj in [[-1, 0], [1, 0], [0, 1], [0, -1]]:
if 0<=i+di<m and 0<=j+dj<n and grid[i+di][j+dj] != -1:
ans += dfs2(i+di, j+dj)
return ans
import sys
lines = sys.stdin.readlines()
m, n = [int(a) for a in lines[0].strip().split(' ')]
grid = []
for line in lines[1:]:
grid.append([int(a) for a in line.strip().split(' ')])
visited = [[0 for _ in range(n)] for _ in range(m)]
for i in range(m):
for j in range(n):
if (i == 0&nbs***bsp;j ==0) and( grid[i][j] == 0 and visited[i][j] == 0):
dfs1(i, j)
# 从下往上求
ans = 0
for j in range(n):
if grid[m-1][j] == 1:
ans = dfs2(i, j)
break
print(ans) 
#include <bits/stdc++.h>
using namespace std;
int mp[1005][1005];
bool vi[1005][1005];
int ans;
int to[][2] = { 0,1,0,-1,1,0,-1,0 };
int n, m;
void dfs1(int x, int y)
{
if (x<0 || y<0 || x>n + 1 || y>m + 1 || vi[x][y] == 1)
return;
mp[x][y] = -1;
vi[x][y] = 1;
for (int i = 0; i < 4; i++)
if (mp[x + to[i][0]][y + to[i][1]] != 1)
dfs1(x + to[i][0], y + to[i][1]);
}
void dfs2(int x, int y)
{
if (vi[x][y] == 1)
return;
vi[x][y] = 1;
ans++;
for (int i = 0; i < 4; i++)
if (mp[x + to[i][0]][y + to[i][1]] != -1)
dfs2(x + to[i][0], y + to[i][1]);
}
int main()
{
int i, j;
while (~scanf("%d%d", &n, &m))
{
memset(mp, -1, sizeof(mp));
memset(vi, 0, sizeof(vi));
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
scanf("%d", mp[i] + j);
dfs1(0, 0);
memset(vi, 0, sizeof(vi));
ans = 0;
dfs2(n, 1);
printf("%d\n", ans);
}
return 0;
} /*用了递归和BFS两种方法实现，但是BFS会超内存限制，递归方法能通过所有测试另外，一开始的使用图像是使用vector<vector<char>>来保存的，这会超内存限制（只能通过92%的测试实例），改为一维数组之后才能通过测试。*/#include <stdlib.h>#include <iostream>#include <vector>#include <queue>usingnamespacestd;/** 将一个值为raw的像素标记为label，并递归的标记其四联通的邻域*/intland = 0;introws, cols;voidlabel_rec(char* data, introw, intcol, charraw, charcolor){land++;// 标记当前像素data[row * cols + col] = color;// 递归的标记四联通像素if(row > 0 && data[(row - 1)*cols+col] == raw)label_rec(data, row - 1, col, raw, color);if(row < rows - 1 && data[(row + 1)*cols+col] == raw)label_rec(data, row + 1, col, raw, color);if(col > 0 && data[row*cols + col - 1] == raw)label_rec(data, row, col - 1, raw, color);if(col < cols-1 && data[row*cols + col + 1] == raw)label_rec(data, row, col + 1, raw, color);}/** 将一个值为raw的像素标记为label，并使用广度优先搜索标记其四联通的邻域*/voidlabel_bfs(char* data, introw, intcol, charraw, charcolor){land++;// data[row][col] = color;queue<pair<int, int>> Q;Q.push(make_pair(row, col));while(!Q.empty()){pair<int, int> coord = Q.front();Q.pop();if(data[coord.first*cols + coord.second] == raw){data[coord.first*cols + coord.second] = color;}// 把四联通邻域中未被标记的加入队列if(coord.first > 0 && data[(coord.first - 1)*cols + coord.second] == raw)Q.push(make_pair(coord.first - 1, coord.second));if(coord.first < rows - 1 && data[(coord.first + 1)*cols + coord.second] == raw)Q.push(make_pair(coord.first + 1, coord.second));if(coord.second > 0 && data[coord.first*cols + coord.second - 1] == raw)Q.push(make_pair(coord.first, coord.second - 1));if(coord.second < cols - 1 && data[coord.first*cols + coord.second + 1] == raw)Q.push(make_pair(coord.first, coord.second + 1));}}intmain(){// 输入数据cin >> rows >> cols;char* image = newchar[rows*cols];for(inti = 0; i < rows; i++){for(intj = 0; j < cols; j++){intpixel;cin >> pixel;image[i*cols + j] = (char)pixel;}}// 先从上、左、右三个边界开始，按照四联通的规则标记海面// 因为在边界处的海面肯定是不被陆地包围的，将海面标记为-1， 防止重复标记for(inti = 0; i < cols; i++){ // 最上面边界if(image[i] == 0)label_rec(image, 0, i, 0, -1);}for(inti = 0; i < rows; i++){ // 最左面边界if(image[i*cols] == 0)label_rec(image, i, 0, 0, -1);}for(inti = 0; i < rows; i++){ // 最右面边界if(image[(i+1)*cols - 1] == 0)label_rec(image, i, cols - 1, 0, -1);}// 未标记的海面为地中海，标记为陆地for(inti = 0; i < rows; i++){for(intj = 0; j < cols; j++){if(image[i*cols + j] == 0)image[i*cols + j] = 1;}}land = 0;for(inti = 0; i < rows; i++){ // 从最下边界开始递归的标记为陆地if(image[(rows - 1)*cols + i] == 1){label_rec(image, rows - 1, i, 1, 2);break; // 之所以要退出，是因为仅仅需要标记与底边陆地相连通的，其他的海中陆地不需要标记}}delete[] image;cout << land << endl;return0;}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
