首页 > 代码库 > The Grove(poj 3182)
The Grove(poj 3182)
题意:一个n*m(n,m<=50)的矩阵有一片连着的树林,Bessie要从起始位置出发绕林子一圈再回来,每次只能向横着、竖着或斜着走一步。问最少需多少步才能完成。
/* 如果我们用搜索来写的话,如果搜出的路径能够包围其中的一个点,那么就能包围森林,这样问题就被简化了。 我们任选一个点作为被包围点,在搜索时利用射线原理判断某这个点是否在多边形中(判断函数需要认真考虑)。 如果这条射线经过多边形奇数次,则在多边形内,否则不在。 */ #include<cstdio> #include<iostream> #include<cstring> #include<queue> #define N 60 using namespace std; char map[N][N],ch[N]; int n,m,sx,sy,gx,gy,nx,ny,tx,ty,dp[N][N][2]; int dx[8]={-1,1,0,0,-1,-1,1,1}; int dy[8]={0,0,-1,1,-1,1,-1,1}; struct node{int x,y,k;}; bool ok(){ if(tx==gx&&ty<gy){ if(nx<tx)return true; } else if(nx==gx&&ny<gy){ if(nx>tx)return true; } return false; } void bfs(){ memset(dp,-1,sizeof(dp)); queue<node> q; node u;u.x=sx;u.y=sy;u.k=0;dp[sx][sy][0]=0;q.push(u); while(!q.empty()){ u=q.front();q.pop();nx=u.x;ny=u.y;int nk=u.k,tk; for(int i=0;i<8;i++){ tx=nx+dx[i];ty=ny+dy[i];tk=nk; if(tx<1||tx>n||ty<1||ty>m||map[tx][ty]==‘X‘)continue; if(ok())tk^=1; if(dp[tx][ty][tk]==-1){ dp[tx][ty][tk]=dp[nx][ny][u.k]+1; node v;v.x=tx;v.y=ty;v.k=tk;q.push(v); } } } printf("%d\n",dp[sx][sy][1]); } int main(){ scanf("%d%d",&n,&m); bool flag=false; for(int i=1;i<=n;i++){ scanf("%s",ch); for(int j=1;j<=m;j++){ map[i][j]=ch[j-1]; if(map[i][j]==‘*‘)sx=i,sy=j; if(!flag&&map[i][j]==‘X‘)flag=1,gx=i,gy=j; } } bfs(); return 0; }
The Grove(poj 3182)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。