Codeforces 193A. Cutting Figure（dfs）

阳光穿透心脏的1/2处 2022-06-02 03:59 95阅读 0赞

You've gotten an *n* × *m* sheet of squared paper. Some of its squares are painted. Let's mark the set of all painted squares as *A*. Set *A* is connected. Your task is to find the minimum number of squares that we can delete from set *A* to make it not connected.

A set of painted squares is called connected, if for every two squares *a* and *b* from this set there is a sequence of squares from the set, beginning in *a* and ending in *b*, such that in this sequence any square, except for the last one, shares a common side with the square that follows next in the sequence. An empty set and a set consisting of exactly one square are connected by definition.

Input

The first input line contains two space-separated integers *n* and *m* (1 ≤ *n*, *m* ≤ 50) — the sizes of the sheet of paper.

Each of the next *n* lines contains *m* characters — the description of the sheet of paper: the *j*\-th character of the *i*\-th line equals either "\#", if the corresponding square is painted (belongs to set *A*), or equals "." if the corresponding square is not painted (does not belong to set *A*). It is guaranteed that the set of all painted squares *A* is connected and isn't empty.

Output

On the first line print the minimum number of squares that need to be deleted to make set *A* not connected. If it is impossible, print -1.

Example

Input

5 4
    ####
    #..#
    #..#
    #..#
    ####

Output

Input

5 5
    #####
    #...#
    #####
    #...#
    #####

Output

Note

In the first sample you can delete any two squares that do not share a side. After that the set of painted squares is not connected anymore.

The note to the second sample is shown on the figure below. To the left there is a picture of the initial set of squares. To the right there is a set with deleted squares. The deleted squares are marked with crosses.

![3278c0137a7ccad8810164c3f93c2a34_v_1514871637][]

题解：

给你个图为一个\#号的连通块，问你至少去掉几个\#可以使图不连通

看起来很难但是找找规律可以发现无论是什么图的答案都是-1,1,或者2，因为去掉最多的情况把图形的角的方格两边连通块去掉就是用2个

那么-1的情况就是\#小于3个的时候

枚举所有\#号位置，如果去掉该位置连通块是2个以上就直接输出1，否则输出2

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<queue>
    #include<stack>
    #include<math.h>
    #include<vector>
    #include<map>
    #include<set>
    #include<stdlib.h>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<stdio.h>
    using namespace std;
    #define ll long long
    int dirx[4]={0,0,-1,1};
    int diry[4]={1,-1,0,0};
    char s[55][55];
    int vis[55][55];
    int n,m,ans;
    void dfs(int x,int y)
    {
        ans++;
        int xx,yy,i;
        for(i=0;i<4;i++)
        {
            xx=dirx[i]+x;
            yy=diry[i]+y;
            if(xx>=0&&yy>=0&&xx<n&&yy<m&&!vis[xx][yy]&&s[xx][yy]=='#')
            {
                vis[xx][yy]=1;
                dfs(xx,yy);
            }
        }
    }
    int main()
    {
        int i,j,num=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++)
        {
            scanf("%s",s[i]);
            for(j=0;j<m;j++)
            {
                if(s[i][j]=='#')
                {
                    num++;
                }
            }
        }
        if(num<3)
        {
            printf("-1\n");
            return 0;
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(s[i][j]=='#')
                {
                    memset(vis,0,sizeof(vis));
                    vis[i][j]=1;
                    ans=0;
                    for(int p=0;p<n;p++)
                    {
                        for(int q=0;q<m;q++)
                        {
                            if(s[p][q]=='#'&&!vis[p][q])
                            {
                                vis[p][q]=1;
                                dfs(p,q);
                                goto loop;
                            }
                        }
                    }
                    loop:;
                    if(ans!=num-1)
                    {
                        printf("1\n");
                        return 0;
                    }
                }
            }
        }
        printf("2\n");
        return 0;
    }

[3278c0137a7ccad8810164c3f93c2a34_v_1514871637]: https://odzkskevi.qnssl.com/3278c0137a7ccad8810164c3f93c2a34?v=1514871637