ACdream 1078 Cutting Figure （dfs）

ゞ浴缸里的玫瑰 2022-06-12 09:58 155阅读 0赞

题目链接：  
[ACdream 1078][]

题意：  
给你一个n∗m 的图， \# 表示存在的点，.  表示无，\#被保证全都连在一起，求最少需要把多少个\#转换成 . ，使得它分成两个部分。

题解：  
其实只有三种情况。  
第一种是‘\#’数量少于3 的情况，这时候不可分割。  
第二种是只需要割一个点就可以的。  
最后一种情况是只需要割两个点就可以。  
然后判断‘\#’个数，如果小于3 ，直接输出−1 。  
否则枚举割一个点的位置，用 dfs  搜一下看‘\#’被分成几部分，如果大于 1  的话直接返回，并输出1 ，否则直接输出2 。

bfs  也可以。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int N = 55;
    int n,m;
    int mp[N][N];
    bool vis[N][N];
    void dfs(int x, int y)
    {
        vis[x][y] = 1;
        if(0 <= x - 1 && mp[x - 1][y] && !vis[x - 1][y])
        {
            dfs(x - 1, y);
        }
    
        if(x + 1 < n && mp[x + 1][y] && !vis[x + 1][y])
        {
            dfs(x + 1, y);
        }
    
        if(0 <= y - 1 && mp[x][y - 1] && !vis[x][y - 1])
        {
            dfs(x, y - 1);
        }
    
        if(y + 1 < m && mp[x][y + 1] && !vis[x][y + 1])
        {
            dfs(x, y + 1);
        }
    
    }
    
    int cal(int x, int y)
    {
        int cnt=0;
        memset(vis, 0, sizeof(vis));
        vis[x][y] = 1;
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(mp[i][j] && !vis[i][j])
                {
                    dfs(i,j);
                    cnt++;
                }
            }       
        }   
        return cnt;
    }
    
    int solve()
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                if(cal(i, j)>1)
                    return 1;
            }
        }
    
        return 0;
    }
    
    int main()
    {
        int cnt = 0;
        char ch;
        scanf("%d%d",&n,&m); 
        for(int i=0; i<n; i++)
        {
            for(int j=0;j<m;j++)
            {
                cin >> ch;
                if(ch=='#')
                {
                    mp[i][j] = 1;
                }
                else
                {
                    mp[i][j] = 0;
                } 
                cnt += mp[i][j];
            }
        }   
        if(cnt<3)
        {
            puts("-1");
        }
        else if(solve())
        {
            puts("1");
        }
        else
        {
            puts("2");
        }
        return 0;
    }

[ACdream 1078]: http://acdream.info/problem?pid=1078