暑期训练赛(6)E

2024-05-11 03:32
文章标签 暑期 训练赛

本文主要是介绍暑期训练赛(6)E,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

C. Cutting Figure
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Sample test(s)
input
5 4
####
#..#
#..#
#..#
####
output
2
input
5 5
#####
#...#
#####
#...#
#####
output
2
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.

//AC代码

/*
从此题可以推出答案只有三种:-1,1,2
首先处理掉-1的情况,也就是初始只有0,1,2个#的情况
然后只需要枚举#,然后进行搜索dfs,判断是否能够做到所有的点就OK了
否则就是2
*/
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
#define LL long long
#define IT __int64
#define zero(x) fabs(x)<eps
#define mm(a,b) memset(a,b,sizeof(a))
const int INF=0x7fffffff;
const double inf=1e8;
const double eps=1e-10;
const double PI=acos(-1.0);
const int MAXN=60;
using namespace std;
int n, m, ps, move[4][2]= {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool isPaint[MAXN][MAXN], isVis[MAXN][MAXN];
void input()
{
cin>>n>>m;
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
{
char c;
cin>>c;
if (c=='#')
{
isPaint[i][j]=true;
ps++;
}
}
}
bool isValid(int x, int y)
{
return 0<=x&&x<n&&0<=y&&y<m;
}
void dfs(int x, int y)
{
isVis[x][y]=true;
for (int i=0; i<4; ++i)
{
int p=x+move[i][0], q=y+move[i][1];
if (isValid(p, q) && isPaint[p][q] && !isVis[p][q])
dfs(p, q);
}
}
bool isConnect()
{
int x, y;
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (isPaint[i][j])
{
x=i;
y=j;
}
memset(isVis, false, sizeof(isVis));
dfs(x, y);
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (isPaint[i][j] && !isVis[i][j])
return false;
return true;
}
int main()
{
input();
if (ps==1 || ps==2)
{
cout<<-1<<endl;
return 0;
}
for (int i=0; i<n; ++i)
for (int j=0; j<m; ++j)
if (isPaint[i][j])
{
isPaint[i][j]=false;
if (!isConnect())
{
cout<<1<<endl;
return 0;
}
isPaint[i][j]=true;
}
cout<<2<<endl;
return 0;
}


 

这篇关于暑期训练赛(6)E的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/978385

相关文章

暑期学习总结

iOS学习 前言无限轮播图换头像网络请求按钮的configuration属性总结 前言 经过暑期培训,完成了五个项目的仿写,在项目中将零散的内容经过实践学习,有了不少收获,因此来总结一下比较重要的内容。 无限轮播图 这是写项目的第一个难点,在很多项目中都有使用,越写越熟练。 原理为制造两个假页,在首和尾分别制作最后一页和第一页的假页,当移动到假页时,使用取消动画的方式跳到

腾讯暑期实习笔经面经-为你准备(独家资料)

2012腾讯暑期实习笔经面经,技术类 内容逐渐补充。 ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -- 以下一段话来源

【iOS】暑期学习总结

暑期学习总结 前言无限轮播图换头像简单的网络请求UISearchController 前言 暑假在学校完成了五个项目,总的来说学习到了很多新的知识,这里对暑假中学习的内容进行一个小的总结,整理一些个人认为比较重点的内容。 无限轮播图 无限轮播图的原理是在轮播的图片两边加上两个假页,通过判断是否到了这两个假页的位置,而后将滚动视图展示位置移动,从而可以实现视觉效果上的无限轮播效

暑期培训计划之个人计划

使用算法竞赛入门经典(刘汝佳编) 暑期培训计划之个人计划(7.22到8.13) 日期 周次         看书                                                      编程题目                                 看书完成情况                        题目完成情况         备注

训练赛3

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2348&cid=1232 题意: 有两个磁盘,第一个磁盘有n个安装包,第二个磁盘有m个安装包。有些安装包的安装依赖于其他安装包的安装,即如果x依赖与y,那么包y必须在包x之前安装,每次可以插入这两张磁盘中的一张去安装一些包,求以最小的交换次数安装好所有的包,保证依赖关系不存在环,开始插入和最

训练赛 Grouping(强连通分量缩点 + DAG求最长路)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=158#problem/F 大致题意:给出n个人和m种关系(ti,si),表示ti的年龄不小于si。问最小能被划分为几个集合,每个集合都要满足里面的人都无法比较。 思路:对于一条路上的点,它们必定不能被划分到同一个集合中,因此原题变为求一条最长路。而题目中有可能出现

2024牛客暑期多校训练营7 D.Interval Selection(异或哈希+双指针)

原题链接:D.Interval Selection 题目大意: 给你一个长度为 n n n 的数组 a a a,定义一个区间 [ l , r ] [l,r] [l,r] 内的连续子数组为好的,当且仅当这个子数组内的所有元素 a l , a l + 1 , . . . , a r a_{l},a_{l+1},...,a_{r} al​,al+1​,...,ar​ 在当前区间中恰好

暑期算法训练

目录 A.糖果(Candy) B.小红的数组重排  C.牛牛与LCM D.子串 E.勤奋的杨老师  F.清楚姐姐跳格子  G.方块 I  H.PUBG  A.糖果(Candy) 思路 :贪心,为了使操作数最少,我们要尽可能的先吃第二个盒子里的糖果,如果还不满足条件就再吃第一个盒子里的糖果。 C++代码: void solve(){int n,x;cin

hdu5289 Assignment --2015多校训练赛(一)

题意: 给定一串数字,里面存在多少个区间[l, r] 使得里面的最大值与最小值之差小于k。 思路: 用RMQ预处理出所有区间的最大值与最小值之差。之后枚举左端点L, 二分处理差值小于k的最左边端点R,把所有 的R-L+1加上就是答案。 /************************************************ Author: fisty* Create

《白蛇:浮生》后劲不足,国漫败走2024暑期档

截止到8月19日中午,上映10天的动画电影《白蛇:浮生》票房终于突破3亿。 客观来说,3亿票房在今年暑期档不算差,但对于上映首日就拿到1.29亿票房的《白蛇:浮生》而言,后期票房走势确实没有达到预期,猫眼预测票房也从点映期间的6.62亿掉到了如今的5.44亿,大概率很难超过《白蛇2:青蛇劫起》的5.7亿票房。 作为追光动画“白蛇”系列的第三部作品,IP本身已经积累了一部分固