題目鏈接：點擊查看

題目大意：給出一個 n * m 的矩陣，' # ' 代表黑色方格，' . ' 代表白色方格，現在可以在任意方格上擺放任意個單向磁鐵，磁鐵具有的一個性質是：每秒鐘 N 極磁鐵會向同行或同列的?S 極磁鐵靠攏，但 S 極磁鐵不會移動，需要構造一種方案，使得：

無論如何移動，N 極磁鐵都無法到達白色方格

存在一種移動方案，使得 N 極磁鐵可以遍歷所有黑色方格

每一行、每一列至少存在一個 S 極磁鐵

N 極磁鐵的個數盡可能少

輸出最少的 N 極磁鐵的個數

題目分析：圖論的題，看完五個樣例之后心里大概有點想法了，首先根據第二個樣例與其余四個樣例的對比，不難看出的一個小結論就是：每一行或每一列至多存在一個黑色方格組成的線段，因為如果存在兩個黑色方格組成的線段的話，他們肯定會跨過其中的白色方格可以互相到達，也就是存在一種方案會到達白色方格，與題意不符

再就是通過樣例四和樣例五可以知道，在滿足上面結論的前提下，對于全部都是白色方格的行或列也有限制，如果存在著全白的行，但不存在著全白的列的話，那么全白的行內如果放置 S 極磁鐵，就不能滿足條件 1 ，如果不放置 S 極磁鐵，就不能滿足條件 3 ，無論怎么樣都不能滿足條件，所以是不行的，同理將行和列反過來想也是一樣的

只有在滿足黑色方格的條件下，不存在這全白的列和行，或者同時存在著全白的列和行才行，如果同時存在著全白的列和行的話，可以將 S 極磁鐵放置在全白列和全白行的交界處，這樣既能滿足條件 1 ，也能滿足條件 4

最后總結一下上面的三段話：

每一行或每一列至多存在一個黑色方格組成的線段

不存在著全白的列和行

同時存在著全白的列和行

只有同時滿足上述三個條件，題目才存在著解，否則都是 -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("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1344D Monopole Magnets(dfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。