CodeForces – 1344D Monopole Magnets(dfs)Falcon的博客-

题目链接：点击查看

题目大意：给出一个 n * m 的矩阵，’ # ‘ 代表黑色方格，’ . ‘ 代表白色方格，现在可以在任意方格上摆放任意个单向磁铁，磁铁具有的一个性质是：每秒钟 N 极磁铁会向同行或同列的 S 极磁铁靠拢，但 S 极磁铁不会移动，需要构造一种方案，使得：

1. 无论如何移动，N 极磁铁都无法到达白色方格
2. 存在一种移动方案，使得 N 极磁铁可以遍历所有黑色方格
3. 每一行、每一列至少存在一个 S 极磁铁
4. N 极磁铁的个数尽可能少

输出最少的 N 极磁铁的个数

题目分析：图论的题，看完五个样例之后心里大概有点想法了，首先根据第二个样例与其余四个样例的对比，不难看出的一个小结论就是：每一行或每一列至多存在一个黑色方格组成的线段，因为如果存在两个黑色方格组成的线段的话，他们肯定会跨过其中的白色方格可以互相到达，也就是存在一种方案会到达白色方格，与题意不符

再就是通过样例四和样例五可以知道，在满足上面结论的前提下，对于全部都是白色方格的行或列也有限制，如果存在着全白的行，但不存在着全白的列的话，那么全白的行内如果放置 S 极磁铁，就不能满足条件 1 ，如果不放置 S 极磁铁，就不能满足条件 3 ，无论怎么样都不能满足条件，所以是不行的，同理将行和列反过来想也是一样的

只有在满足黑色方格的条件下，不存在这全白的列和行，或者同时存在着全白的列和行才行，如果同时存在着全白的列和行的话，可以将 S 极磁铁放置在全白列和全白行的交界处，这样既能满足条件 1 ，也能满足条件 4

最后总结一下上面的三段话：

1. 每一行或每一列至多存在一个黑色方格组成的线段
2. 不存在着全白的列和行
3. 同时存在着全白的列和行

只有同时满足上述三个条件，题目才存在着解，否则都是 -1 ，这三个条件通过给出的五个样例应该不难分析出来

然后就是如何求解呢，根据样例三可以大胆猜测是需要求连通块的个数，因为 N 极磁铁无法斜着移动，所以每一个连通块内全部放置 S 极磁铁，然后放一个 N 极磁铁就够了

代码：

 #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;  typedef long long LL;  typedef unsigned long long ull;  const LL inf=0x3f3f3f3f;  const int N=1e3+100;  const int b[4][2]={0,1,0,-1,1,0,-1,0};  char maze[N][N];  int n,m;  bool check_blank()//检查空白行或列是否满足条件  {  bool flag_row=false,flag_col=false;  for(int i=1;i<=n;i++)  {   bool flag=false;   for(int j=1;j<=m;j++)   {    if(maze[i][j]=='#')    {     flag=true;     break;    }   }   if(!flag)    flag_row=true;//存在空白的一行   }  for(int j=1;j<=m;j++)  {   bool flag=false;   for(int i=1;i<=n;i++)   {    if(maze[i][j]=='#')    {     flag=true;     break;    }   }   if(!flag)    flag_col=true;//存在空白的一列   }  return flag_row&&!flag_col||!flag_row&&flag_col; }  bool check_black()//检查黑色线段是否满足条件 {  for(int i=1;i<=n;i++)  {   int cnt=0;   for(int j=1;j<=m;j++)   {    if(maze[i][j]=='#')    {     cnt++;     while(j<=m&&maze[i][j]=='#')      j++;    }   }   if(cnt>1)    return true;  }  for(int j=1;j<=m;j++)  {   int cnt=0;   for(int i=1;i<=n;i++)   {    if(maze[i][j]=='#')    {     cnt++;     while(i<=n&&maze[i][j]=='#')      i++;    }   }   if(cnt>1)    return true;  }  return false; }  void dfs(int x,int y)//dfs求连通块 {  maze[x][y]='.';  for(int i=0;i<4;i++)  {   int xx=x+b[i][0];   int yy=y+b[i][1];   if(xx<=0||yy<=0||xx>n||yy>m)    continue;   if(maze[xx][yy]=='.')    continue;   dfs(xx,yy);  } }  int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);  scanf("%d%d",&n,&m);  for(int i=1;i<=n;i++)   scanf("%s",maze[i]+1);  if(check_blank()||check_black())   return 0*puts("-1");  int ans=0;  for(int i=1;i<=n;i++)   for(int j=1;j<=m;j++)    if(maze[i][j]=='#')    {     ans++;     dfs(i,j);    }  printf("%dn",ans);            return 0; }