首页 > 试题广场 >

分割后处理

[编程题]分割后处理
  • 热度指数:1391 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

研究地球空间科学的永强想研究海岸线的长度和海岸线面积之间的关系,为此他找来了很多航拍图像。在航拍图像上利用图像分割的方法,把图像的每个像素标记成陆地(1)和水面(0)。

示例图片:


现在永强想知道每张图中陆地部分的面积。


已知每张图最底部的一条边都是陆地,并且在一张图上陆地都是四邻域联通的。

但是永强发现分割的结果有很多的噪声,于是他定义了如下规则试图去除噪声:
a)    如果一个水面区域被陆地包围,则将这个区域记为陆地;
b)    在a的基础上如果一个陆地区域不和底边的陆地相连,那么这是一个岛屿,不计入陆地的面积。



输入描述:
第一行为两个整数m和n,
接下来m行每行会有n个数,0表示水面,1表示陆地。


输出描述:
去噪后陆地部分的面积。
示例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;
}
}

发表于 2018-09-07 02:17:32 回复(1)
1.从边缘且为水的位置开始遍历,将所有没有被陆地包围的水标记为2
1 2 2 1 2 2
2 2 1 0 1 2 
1 1 1 1 1 2 
1 0 0 1 1 1 
1 1 1 1 1 1
2.将被陆地包围的水标记为1(陆地)
1 2 2 1 2 2 
2 2 1 1 1 2 
1 1 1 1 1 2 
1 1 1 1 1 1 
1 1 1 1 1 1
3.从下边缘且为陆地的位置开始遍历,标记所有陆地为3,同时计算面积
1 2 2 3 2 2
2 2 3 3 3 2 
3 3 3 3 3 2 
3 3 3 3 3 3 
3 3 3 3 3 3
此时岛屿标记为1,水标记为2,陆地标记为3
#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;
}


发表于 2021-11-21 10:33:31 回复(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; 
}

发表于 2021-08-11 20:16:46 回复(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;
}

发表于 2018-08-17 23:20:38 回复(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;
}

发表于 2018-08-18 23:25:58 回复(9)
#只过了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)
发表于 2020-08-20 19:38:00 回复(0)
## 将所有边缘上的海洋联通起来
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)
python代码通过8.3%, 求问各位大嘎肿么回事
发表于 2020-08-05 21:21:22 回复(1)
基础dfs,想法是先把和外边界连通的0染成-1,然后统计和最下面内边界连通的非-1的个数。
#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;
}



发表于 2019-08-19 13:15:23 回复(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;
}
发表于 2019-03-12 21:47:56 回复(0)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long LL;

int dix[4] = {1,-1,0,0};
int diy[4] = {0,0,-1,1};
struct point
{
    int x,y;
};
int n,m;
int tu[1005][1005],check[1005][1005];;
void dfs(int x,int y)
{
    int i,xx,yy;
    queue<point> qua;
    point p,pp;
    p.x = x,p.y = y;
    check[x][y] = 1;
    qua.push(p);
    while(!qua.empty())
    {
        p = qua.front();
        qua.pop();
        for(i=0;i<4;i++)
        {
            xx = p.x + dix[i];
            yy = p.y + diy[i];
            if(xx<1||xx>n||yy<1||yy>m)
                continue;
            if(tu[xx][yy]==0&&check[xx][yy] == 0)
            {
                pp.x = xx;
                pp.y = yy;
                check[pp.x][pp.y] = 1;
                qua.push(pp);
            }
        }
    }
}
int sum_dfs(int x,int y)
{
    int i,xx,yy;
    int sum=1;
    point p,pp;
    queue<point> qua;
    p.x = x;
    p.y = y;
    qua.push(p);
    check[x][y] = 1;
    while(!qua.empty())
    {
        p = qua.front();
        qua.pop();
        for(i=0;i<4;i++)
        {
            xx = p.x + dix[i];
            yy = p.y + diy[i];
            if(xx<1||xx>n||yy<1||yy>m)
                continue;
            if(tu[xx][yy]==1&&check[xx][yy] == 0)
            {
                pp.x = xx;
                pp.y = yy;
                check[pp.x][pp.y] = 1;
                qua.push(pp);
                sum++;
            }
        }
    }
    return sum;
}
int main()
{
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            cin>>tu[i][j];
    memset(check,0,sizeof(check));
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(i==1||i==n||j==1||j==m)
            {
                if(tu[i][j] == 0&&check[i][j]==0)
                {
                    dfs(i,j);
                }
            }
        }
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            if(check[i][j] == 0)
                tu[i][j]=1;
        }
    }
    memset(check,0,sizeof(check));
    int sum = sum_dfs(n,1);
    cout<<sum<<endl;
    return 0;
}

发表于 2018-10-13 21:53:35 回复(0)