洛谷 题解 P4955 【[USACO14JAN]Cross Country Skiing 越野滑雪】

二分+DFS

看到这么多大佬写了并查集，BFS的，还没有人写DFS版的，那么肯定是要来水水积分的啦毕竟这可是道伪紫题呢!

做法楼上楼下也讲得很清楚了吧，详见代码的注释

#include<bits/stdc++.h> using namespace std; bool taofen_boys[510][510];//你可以理解为tf[][] //是否需要走到 (不要打我 int Map[510][510]; //存每个点的高度 bool vis[510][510];//是否访问到 int n,m; int sx,sy; //起点 int dx[5]={0,0,0,1,-1}; int dy[5]={0,1,-1,0,0}; int mid; vector<pair<int,int> >flag; //用于存需要走到的点 inline int read() {int tot=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9'){tot=tot*10+c-'0';c=getchar();}return tot; } inline void DFS(int x,int y) {//cout<<x<<" "<<y<<endl;for(int i=1;i<=4;i++)//四个方向枚举{int a=x+dx[i],b=y+dy[i];//cout<<a<<" "<<b<<endl;if(a<1||b<1||a>n||b>m||vis[a][b])continue;if(abs(Map[a][b]-Map[x][y])>mid)continue;//是否满足要求vis[a][b]=1;DFS(a,b);//这里不用回溯} } inline bool check() {memset(vis,0,sizeof(vis));vis[sx][sy]=1;DFS(sx,sy);/*for(int i=1;i<=n;i++){for(int j=1;j<=m;j++)cout<<vis[i][j]<<" ";cout<<endl;}*/for(int i=0;i<flag.size();i++){int tx=flag[i].first,ty=flag[i].second;if(!vis[tx][ty])return 0;//判断是否走过}return 1; } int main() {n=read();m=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)Map[i][j]=read();for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){taofen_boys[i][j]=read();if(taofen_boys[i][j]){sx=i,sy=j;//起点随便记录一个就行了flag.push_back(make_pair(i,j));}}/*mid=5000000;check();*/int l=0,r=1000000000,ans=0;while(l<=r)//二分答案{mid=l+r>>1;//cout<<l<<" "<<r<<" "<<mid<<" "<<ans<<" "<<check()<<endl;if(check())r=mid-1,ans=mid;else l=mid+1;}cout<<ans<<endl;return 0; }

转载于:https://www.cnblogs.com/hulean/p/10902642.html

总结

以上是生活随笔为你收集整理的洛谷 题解 P4955 【[USACO14JAN]Cross Country Skiing 越野滑雪】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。