BFS

本题和连通块并无二致，从四个点开始BFS，减去0的个数，减去一开始1的个数，就是剩下在里面的0的个数

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 15;
int g[N][N],ans = 100;

void bfs(int a,int b)
{
    queue<PII> q;
    q.push({a,b});
    ans--;
    g[a][b] = 1;
    while(!q.empty())
    {
        int tx[] = {1,-1,0,0},ty[] = {0,0,1,-1};
        PII t = q.front();
        q.pop();
        int x = t.first,y = t.second;
        for(int i=0;i<4;i++)
        {
            int rx = x+tx[i],ry = y+ty[i];
            if(rx>=1 && rx<=10 && ry>=1 && ry<=10 && g[rx][ry] == 0)
            {
                g[rx][ry] = 1;
                ans--;
                q.push({rx,ry});
            }
        }
    }
}

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

只会DFS搜的废物

思路是在读进去的图四周加一圈0然后随便选个点开始深搜

面积=1数+外圈0数-扩充后周长

#include <bits/stdc++.h>

using namespace std;



int n, m,s=0;

int Map[110][110];

int dir[4][2] = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };

void b(int x,int y){

    for (int i=0;i<4;i++){

        int x1=x+dir[i][0];

        int y1=y+dir[i][1];


        if (x1 >= 0 && x1 <= n+1 && y1 >= 0 && y1 <= m+1 && Map[x1][y1] == 0){

            Map[x1][y1]=-1;

            b(x1,y1);

            s++;

        }
    }
}

int main()

{

        n=10;m=10;

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= m; j++){

                cin >> Map[i][j];

                if (Map[i][j]==1){

                    Map[i][j]=-1;

                    s++;

                }

                }      

        b(0,0);

        cout<<144-s;    

}