1359：围成面积

【题目描述】
编程计算由“”号围成的下列图形的面积。面积计算方法是统计号所围成的闭合曲线中水平线和垂直线交点的数目。如下图所示，在10×10的二维数组中，有“*”围住了15个点，因此面积为15。

【输入】
10×10的图形。

【输出】
输出面积。

【输入样例】
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
【输出样例】
15

分析

1. 刚开始测试点错了，后来发现，给他加上一圈，不然你都不知道入口在哪，因为他可能起点就是1，不让走，不能直接0,0搜；
2. 然后这种求边界包围里面的问题时，我们可以采用vis数组进行标记，最后遍历没有走过的点（记着除去障碍物，走不了的点）；
3. 这个题和：P1162 填涂颜色 java_bfs 几乎一样，只不过最后处理的结果不一样；然后和这道题：1335：【例2-4】连通块”也差不多；

dfs

#include 

using namespace std;

int a[15][15];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[15][15];
int ans = 0;


void dfs(int x, int y) {
    //四个方向去走
    for (int i = 0; i < 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx >= 1 && yy >= 0 && xx <= 11 && yy <= 11 && a[xx][yy] == 0) {
            vis[xx][yy] = 1;
            //这个点搜索，下次就不用再回溯去再搜
            a[xx][yy] = 1;
            dfs(xx, yy);
        }
    }
}

int main() {

    //给他加上一圈，不然你都不知道入口在哪，因为他可能起点就是1，不让走，不能直接0,0搜
    for (int i = 0; i <= 11; ++i) {
        a[0][i] = 0;
        a[i][0] = 0;
        a[11][i] = 0;
        a[i][11] = 0;
    }

    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 1)
                vis[i][j] = 1;
        }
    }
    dfs(0, 0);
    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            if (vis[i][j] == 0)
                ans++;
        }
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

bfs

bfs的思路和上面的例题以及思想差不多，就是递归换成了while循环，把这个这正在搜索的点所能到达的所有点加入队列，以便下一次广搜，从他们再出发向下去搜；

#include 

using namespace std;

int a[15][15];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[15][15];
queue<int> qx;
queue<int> qy;
int ans = 0;


void bfs(int x, int y) {
    //四个方向去走
    qx.push(x);
    qy.push(y);
    while (!qx.empty()) {
        for (int i = 0; i < 4; ++i) {
            int xx = qx.front() + dx[i];
            int yy = qy.front() + dy[i];
            if (xx >= 1 && yy >= 0 && xx <= 11 && yy <= 11 && a[xx][yy] == 0) {
                vis[xx][yy] = 1;
                a[xx][yy] = 1;
                qx.push(xx);
                qy.push(yy);
            }
        }
        qx.pop();
        qy.pop();
    }

}

int main() {

    //给他加上一圈，不然你都不知道入口在哪，因为他可能起点就是1，不让走，不能直接0,0搜
    for (int i = 0; i <= 11; ++i) {
        a[0][i] = 0;
        a[i][0] = 0;
        a[11][i] = 0;
        a[i][11] = 0;
    }

    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 1)
                vis[i][j] = 1;
        }
    }
    bfs(0, 0);
    for (int i = 1; i <= 10; ++i) {
        for (int j = 1; j <= 10; ++j) {
            if (vis[i][j] == 0)
                ans++;
        }
    }
    cout << ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62