[1]1270海战

题目描述

在这个著名的游戏中，在一个方形的盘上放置了固定数量和形状的船只，每只船却不能碰到其它的船。在这个题中，我们仅考虑船是方形的，所有的船只都是由图形组成的方形。编写程序求出该棋盘上放置的船只的总数。
输入
输入文件头一行由用空格隔开的两个整数R和C组成，1< =R,C< =1000，这两个数分别表示游戏棋盘的行数和列数。接下来的R行每行包含C个字符，每个字符可以为“#”，也可为“.”，“#”表示船只的一部分，“.”表示水。
输出
为每一个段落输出一行解。如果船的位置放得正确（即棋盘上只存在相互之间不能接触的方形，如果两个“#”号上下相邻或左右相邻却分属两艘不同的船只，则称这两艘船相互接触了）。就输出一段话“There are S ships.”,S表示船只的数量。否则输出“Bad placement.”。

样例输入

6 8
…#.#
##…#
##…#
…#
#…#
#…#…#

样例输出

There are 5 ships.

提示
思路

dfs连通块， 套模板 

void dfs(int x,int y){
    a[x][y]='.';
    int i,j;
    for(i = 1; i <= 4; i++){
        int xx= x+ix[i];
        int yy =y+iy[i];
        if(xx>0 && xx<=n && yy>0 && yy<=m && a[xx][yy] == '#'){
            dfs(xx,yy);
        }
    }
    return ;
}

要注意特判的情况，即这道题的难点在于判断是否有船相邻。 通过自己模拟的数据可以得出结论： 如果图是不和法的，一定存在如下结构： 

# #   或 # #  或 # #  或  . #
. #      # .     # .      # #
即在一个2*2的方格中有三个#（暴力）

#include <bits/stdc++.h>
using namespace std;
int ix[5] = {0,1,0,-1,0};
int iy[5] = {0,0,1,0,-1};
int n,m,s;
char a[1005][1005];
bool check(int x,int y)//特判Bad placement的情况
{
int c(0);
if(a[x][y]=='#')
{
c++;
}
if(a[x+1][y]=='#')
{
c++;
}
if(a[x][y+1]=='#')
{
c++;
}
if(a[x+1][y+1]=='#')
{
c++;
}
if(c==3)
{
return 0;
}
return 1;
}
void dfs(int x,int y){
a[x][y]='.';
int i,j;
for(i = 1; i <= 4; i++){
int xx= x+ix[i];
int yy =y+iy[i];
if(xx>0 && xx<=n && yy>0 && yy<=m && a[xx][yy] == '#'){

dfs(xx,yy);
}
}
return ;
}
int main()
{
int i,j;
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(i<n && j<m && check(i,j)==0)
{
cout<<"Bad placement."<<endl;
return 0;
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(a[i][j]=='#')
{
s++;
dfs(i,j);
}
}
}
cout<<"There are "<<s<<" ships."<<endl;
return 0;

}
```

#### [2]2927 打击犯罪(black)题目描述

题目描述

某个地区有n(n≤1000)个犯罪团伙，当地警方按照他们的危险程度由高到低给他们编号为1-n，他们有些团伙之间有直接联系，但是任意两个团伙都可以通过直接或间接的方式联系，这样这里就形成了一个庞大的犯罪集团，犯罪集团的危险程度由集团内的犯罪团伙数量唯一确定，而与单个犯罪团伙的危险程度无关（该犯罪集团的危险程度为n）。现在当地警方希望花尽量少的时间（即打击掉尽量少的团伙），使得庞大的犯罪集团分离成若干个较小的集团，并且他们中最大的一个的危险程度不超过n/2。为达到最好的效果，他们将按顺序打击掉编号1到k的犯罪团伙，请编程求出k的最小值。

输入

第一行一个正整数n。接下来的n行每行有若干个正整数，第一个整数表示该行除第一个外还有多少个整数，若第i行存在正整数k，表示i，k两个团伙可以直接联系。

输出

一个正整数，为k的最小值。

样例输入

7
2 2 5
3 1 3 4
2 2 4
2 2 3
3 1 6 7
2 5 7
2 5 6

样例输出

1

【提示】

输出1（打击掉犯罪团伙）

思路

需要注意题目里说的是按顺序打击犯罪团伙，即从1开始打击，要求k尽量小，
因为要求犯罪危险程度小于n/2，因此用一个数组保存，作为判断依据，

网上题解交代如果正向枚举要一直更新并查集，因此使用倒序枚举，具体实现步骤见代码
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctype.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#include<list>
#include<fstream>
using namespace std;
#define N 1010
// 如果正向建立并查集，正向删除，那么每一次都需要维护重置并查集。
//所以我们可以倒过来思考，从n到1枚举，
//每次把i点加入图中，也就是删除1~k-1条边，剩余k~n，若最大集合点数不超过n/2，说明这种方案可行，且k还能小，
//一旦不满足，意味这k不能加入图中，即k即为最小删除边。
int fa[N],a[N][N],c[N];
//fa[i]表示i所在集合的根，c[i]表示i所在集合的总个数
int find(int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)  //初始化
{
fa[i]=i;
c[i]=1;
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i][0]);
for(int j=1;j<=a[i][0];j++)
scanf("%d",&a[i][j]);
}
for(int i=n;i>=1;i--)  //倒着枚举
{
for(int j=1;j<=a[i][0];j++)
if(a[i][j]>i)
//因为是按顺序删除，这里假设i点在图中，所以接下来合并的点必须比i大,
{
int r1=find(i),r2=find(a[i][j]);
if(r1!=r2)
{
fa[r2]=r1;//这里是把i加入到图中
c[r1]+=c[r2];
if(c[i]>(n>>1))
//集合点数超过n/2，k不能进入图中，必须删k
{
cout<<i<<endl;
return 0;
}
}
}
}
return 0;
}