本文主要是介绍【2016-2017 ACM-ICPC (ECNA 2016) H】Vin Diagrams(dfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/gym/101196
题目大意：有一张图，里面有两个凸边形，分别是A和B，求只被A包住的点的个数，只被B包住的点的个数，以及同时被A和B包住的点的个数。
题目思路：刚开始我的想法是先抠出A和B以后，然后对于每一行，分别设立flag1和flag2，如果是奇数次穿过A的某段，那就在下一次遇到.的时候记，然后在偶数次经过A的某段的时候，加给只被A包住的点的个数，如果奇数次的时候遇到了B的某段，那就直接先加给A的某段，然后遇到下一个偶数次的时候加给同时被A和B包住的点的个数，B反之，分了好多好多类，最后还是一直wa7，至今不知道为啥，有、难受。
后来看了网上题解，发现了一个更牛B的做法，抠出A和B以后，可以发现，从上到下，从左到右的第一个属于AorB的点，它的右下角的第一个点一定属于AorB，那么就从这个点出发，直接把A包住的所有点管它是X还是.全给标上，然后再给B包住的所有点都包上，然后遍历整个图，如果他只属于A就加给A，只属于B就加给B，同时属于这俩就加给记录同时被包住的那个变量。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 1e2+5;
int n,m,ans[5];
char mp[MAXN][MAXN];
bool vis[MAXN][MAXN][2],vis2[MAXN][MAXN][2];
int dir[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int x,int y,int col,int pre){int num=0;rep(i,0,3){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy][col]&&mp[xx][yy]!='.'){num++;}}if(num==3){vis[x+dir[pre][0]][y+dir[pre][1]][col]=1;dfs(x+dir[pre][0],y+dir[pre][1],col,pre);}else if(num>0){rep(i,0,3){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy][col]&&mp[xx][yy]!='.'){vis[xx][yy][col]=1;dfs(xx,yy,col,i);}}}
}
void dfs1(int x,int y,int col){rep(i,0,3){int xx=x+dir[i][0];int yy=y+dir[i][1];if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy][col]&&!vis2[xx][yy][col]){vis2[xx][yy][col]=1;dfs1(xx,yy,col);}}
}
void solve(int x){rep(i,1,n){rep(j,1,m){if(vis[i][j][x]){dfs1(i+1,j+1,x);return;}}}
}
int main(){while(~scanf("%d%d",&n,&m)){int sa,ta,sb,tb;memset(vis,0,sizeof(vis));memset(vis2,0,sizeof(vis2));memset(ans,0,sizeof(ans));rep(i,1,n){scanf("%s",mp[i]+1);rep(j,1,m){if(mp[i][j]=='A')sa=i,ta=j;if(mp[i][j]=='B')sb=i,tb=j;}}vis[sa][ta][0]=1;dfs(sa,ta,0,-1);vis[sb][tb][1]=1;dfs(sb,tb,1,-1);solve(0);solve(1);rep(i,1,n){rep(j,1,m){if(mp[i][j]=='.'){int pos=0;if(vis2[i][j][0])pos++;if(vis2[i][j][1])pos+=2;ans[pos]++;}}}printf("%d %d %d\n",ans[1],ans[2],ans[3]);}return 0;
}
这篇关于【2016-2017 ACM-ICPC (ECNA 2016) H】Vin Diagrams(dfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
