本文主要是介绍割点的距离分层解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
割点定义
- 在图中去掉该点使图变为非连通图的点叫做割点
- 割点可以将图分为易于分开处理并且易于合并问题的子图
平面图的距离分层
- 在平面图中将所有点按距一个点的距离进行分层可以高效的处理割点
性质
- 令平面图中距源点距离为x的点的层数为x
- 在平面图中，层数为x的点只能由层数为x-1的点到达
- 若某个层数只有一个点，且图为连通图，那么该点一定为该图的割点
Problem
Codeforces583D判断平面图路径上是否有割点
传送门
先正反dfs求出路径上可行点，然后判断可行点中有无割点
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=2000000+10;
vector<char>A[maxn];
vector<int>vis1[maxn];
vector<int>vis2[maxn];
int n,m;
int X[4]={0,1,0,-1};
int Y[4]={1,0,-1,0};
int cnt[maxn];
inline void floodfill(int x,int y){if(x<0||x>=n||y<0||y>=m)return ;if(vis1[x][y]||A[x][y]=='#')return ;vis1[x][y]++;if(x==n-1&&y==m-1)return;for(int i=0;i<2;i++)floodfill(x+X[i],y+Y[i]);
}
inline void fillflood(int x,int y){if(x<0||x>=n||y<0||y>=m)return ;if(vis2[x][y]||A[x][y]=='#')return ;vis2[x][y]++;if(x==0&&y==0)return;for(int i=2;i<4;i++)fillflood(x+X[i],y+Y[i]);
}
inline void gn(char &x){x=getchar();while(x!='.'&&x!='#')x=getchar();
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);scanf("%d %d",&n,&m);char x;for(int i=0;i<n;i++){for(int j=0;j<m;j++){gn(x);A[i].push_back(x);}}for(int i=0;i<n;i++){for(int j=0;j<m;j++){vis1[i].push_back(0);vis2[i].push_back(0);}}floodfill(0,0);fillflood(n-1,m-1);for(int i=0;i<n;i++){for(int j=0;j<m;j++)if(vis1[i][j]&&vis2[i][j])cnt[i+j]++;}if(!vis1[n-1][m-1]){puts("0");return 0;}for(int i=1;i<n+m-2;i++){if(cnt[i]==1){puts("1");return 0;}}puts("2");
return 0;
}
这篇关于割点的距离分层解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
