首页 > 代码库 > 【POJ3182】The Grove BFS 最短环绕路径
【POJ3182】The Grove BFS 最短环绕路径
题意:给出一个N*M的图,其中‘X’表示树木(树木一定聚集在一起成为森林,不会分开),然后‘.’表示空地,‘*’表示起点,现在要求从起点出发,绕森林一圈,最后回到起点,所经过最少点数。
题目中给的‘+’就是其中一种最短路径。
题解:随便找一条经过森林且不经过起点的直线,可证路径一定会穿过这条直线,那么就在这条直线上枚举一个点,做两遍BFS,求其从分别直线两侧出发到起点的最短距离。
在这里说一个判断边界的简单方法,就是先给图里每个点打上标记,详见代码里‘in’数组,in值为0的自然就不再里面,而没有必要判断什么“1<=x&&x<=n&&……”。
好了,贴代码。
#include <queue> #include <cstdio> #include <cstring> #include <algorithm> #define N 55 #define inf 0x3f3f3f3f using namespace std; const int dx[8]={-1,-1,-1,0,0,1,1,1}; const int dy[8]={-1,0,1,-1,1,-1,0,1}; struct Lux { int x,y; Lux(int a,int b):x(a),y(b){} Lux(){} }; char mp[N][N]; int map[N][N];/*0可行,1森林,2枚举线段,3起点*/ int n,m,ans=inf; int dist[N][N],tx,ty; int in[N][N],cnt; queue<Lux>q; int bfs(int sx,int sy) { int i,fr,ret; int vx,vy; for(ret=fr=0;fr<2;fr++) { memset(dist,0x3f,sizeof(dist)); while(!q.empty())q.pop(); for(i=fr*5;i<fr*5+3;i++) { vx=sx+dx[i]; vy=sy+dy[i]; if(in[vx][vy]&&!map[vx][vy])dist[vx][vy]=1,q.push(Lux(vx,vy)); } while(!q.empty()) { Lux U=q.front();q.pop(); for(i=0;i<8;i++) { vx=U.x+dx[i]; vy=U.y+dy[i]; if(in[vx][vy]&&!map[vx][vy]&&dist[vx][vy]>dist[U.x][U.y]+1) { dist[vx][vy]=dist[U.x][U.y]+1; q.push(Lux(vx,vy)); } } } ret+=dist[tx][ty]; } return ret; } int main() { // freopen("test.in","r",stdin); int i,j,x,y; scanf("%d%d",&n,&m); for(i=1;i<=n;i++)scanf("%s",mp[i]+1); for(j=1;j<=m;j++)for(i=1;i<=n;i++) { in[i][j]=++cnt; if(mp[i][j]=='X') { map[i][j]=1; x=i;y=j; } else if(mp[i][j]=='*')tx=i,ty=j; } if(tx==x&&ty>y) { for(i=y;mp[x][i]=='X';i--); y=i; for(i=y;i;i--)map[x][i]=3; for(i=y;i;i--)ans=max(ans,bfs(x,i)); } else { for(i=y+1;i<=m;i++)map[x][i]=3; for(i=y+1;i<=m;i++)ans=min(ans,bfs(x,i)); } printf("%d\n",ans); return 0; }
【POJ3182】The Grove BFS 最短环绕路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。