1024问

CodeForces - 1344D Monopole Magnets(dfs)

Hester ·
更新时间:2024-11-10
· 671 次阅读

题目链接：点击查看

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

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

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

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

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

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

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

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

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

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

代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include 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(j1) 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(i1) 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||yyn||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("%d\n",ans); return 0; } Frozen_Guardian 原创文章 743获赞 46访问量 5万+ 关注 私信 展开阅读全文
作者：Frozen_Guardian



4d CodeForces dfs

1024 个赞
编辑 举报
需要 登录 后方可回复, 如果你还没有账号请 注册新账号
相关文章
Eclipse 安装插件
Blossom 2020-07-09
672
ASP.NET之Response.Cookies.Remove 无法删除COOKIE的原因
Kefira 2020-07-10
864
asp连接access、sql数据库代码及数据库操作代码
Hazel 2020-02-13
504
CodeForces - 1327E（dp）
Nerissa 2020-04-01
531
CodeForces - 1344D Monopole Magnets(dfs)
Hester 2020-08-20
671
CF 1344 B Monopole Magnets 分析+dfs判联通快
Saadiya 2020-12-08
903
LibreOJ-dfs序2 (dfs序，线段树）
Nova 2021-07-10
562
codeforces C. Hilbert's Hotel
Dora 2020-10-10
736
leetcode中DFS与BFS算法在数组和字符串中的应用
Zahirah 2020-06-05
585
Java实现 LeetCode 827 最大人工岛（DFS+暴力模拟）
Celandine 2020-12-12
944
Special Permutation CodeForces - 1352G（构造）
Rhoda 2020-03-01
625
PHP实现深度优先搜索算法(DFS,Depth First Search)详解
Phemia 2021-01-15
783
基于python模拟bfs和dfs代码实例
Lacie 2020-07-03
675
最短时间学会基于C++实现DFS深度优先搜索
Paula 2021-12-16
1737
C++验证LeetCode包围区域的DFS方法
Ros 2021-12-16
1729
C++ DFS算法实现走迷宫自动寻路
Cybill 2021-12-16
1084
win10系统不能更改pin码错误代码0x801c004d怎么办?
Aurora 2022-01-19
334
苹果 macOS Monterey 12 开发者预览版 Beta 8(21A5534d)发布，修复虚拟机问题
Clementine 2022-02-23
405
C++实现图的遍历算法(DFS,BFS)的示例代码
Jayne 2022-11-04
428
Java搜索与图论之DFS和BFS算法详解
Elina 2022-11-23
953