【洛谷P1457】【USACO2.1.3】城堡【DFS】

本文主要是介绍【洛谷P1457】【USACO2.1.3】城堡【DFS】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：
洛谷：https://www.luogu.org/problemnew/show/P1457
USACO：http://train.usaco.org/usacoprob2?a=K2AezsnHYp9&S=castle

---

给出一个$m\times n$的矩阵，求四个内容：

1. 联通块的个数
2. 最大的联通块的块的个数
3. 去掉任意一扇墙能得到的最大的联通块的块的个数
4. 去掉哪一面墙得到第3问结果。

其中，第四问有多解时选最靠西的，仍然有多解时选最靠南的。同一格子北边的墙比东边的墙更优先。
这道题的读入很特殊。读入方式请见洛谷说明。（楼上链接）

---

思路：

额，这道题其实n久以前老师就叫我们做了。但是就是迟迟没有做。知道现在刷USACO才补上。
对于第一问和第二问，就是细胞问题的模板题。
对于第三问和第四问，我们就先枚举每一个格子的北边的墙，再枚举东边的墙，因为“同一格子北边的墙比东边的墙更优先”。
由于“有多解时选最靠西的，仍然有多解时选最靠南的”，所以就要先从左往右枚举每一列（西），再从下往上枚举每一行（南）。
所以枚举的过程是这样的：

 for (int j=1;j<=m;j++)for (int i=n;i>1;i--)  //第一行没有北边的墙，可以不用枚举{处理北边的墙}for (int j=1;j<m;j++)  //第m列没有东边的墙，可以不用枚举for (int i=n;i>=1;i--){处理东边的墙}

每次如果确定这个格子北边（东边）有墙，就现将这个抢拆掉（$a[i][j]-=4$或$a[i][j]-=2$），跑一边细胞问题，然后再加回来。

---

代码：

/*
ID:ssl_zyc2
TASK:castle
LANG:C++
*/#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 60
using namespace std;const int dx[]={0,0,-1,0,1};
const int dy[]={0,-1,0,1,0};
const int way[]={0,1,2,4,8};
int a[N][N],n,m,ans,sum,cnt;
bool vis[N][N];struct node  //记录答案
{int x,y;char c;
}ANS;void dfs(int x,int y)  //细胞问题模板
{if (x<1||y<1||x>n||y>m) return;if (vis[x][y]) return;vis[x][y]=1;sum++;for (int i=1;i<=4;i++)if ((a[x][y]&way[i])==0)   //这一面有墙（二进制下按位与）dfs(x+dx[i],y+dy[i]);
}int main()
{scanf("%d%d",&m,&n);  //注意是m和n！！！for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)scanf("%d",&a[i][j]);for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)if (!vis[i][j]){sum=0;dfs(i,j);ans=max(ans,sum);cnt++;}printf("%d\n%d\n",cnt,ans);  //前2问ans=0;for (int j=1;j<=m;j++)for (int i=n;i>1;i--){sum=0;memset(vis,0,sizeof(vis));if ((a[i][j]&2)==0) continue;  //本来就没有这一面墙a[i][j]-=2;  //拆墙dfs(i,j);a[i][j]+=2;if (sum>ans)  //记录最优答案{ans=sum;ANS.c='N';ANS.x=i;ANS.y=j;}}for (int j=1;j<m;j++)for (int i=n;i>=1;i--){sum=0;memset(vis,0,sizeof(vis));if ((a[i][j]&4)==0) continue;a[i][j]-=4;dfs(i,j);a[i][j]+=4;if (sum>ans||(sum==ans&&(j<ANS.y||(j==ANS.y&&i>ANS.x)))){ans=sum;ANS.c='E';ANS.x=i;ANS.y=j;}}printf("%d\n%d %d ",ans,ANS.x,ANS.y);putchar(ANS.c);printf("\n");return 0;
}

这篇关于【洛谷P1457】【USACO2.1.3】城堡【DFS】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---