栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 3182 The Grove

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 3182 The Grove

#include <queue>#include <cstdio>#include <cstring>#include <algorithm>#define N 55#define inf 0x3f3f3f3fusing 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];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("%dn",ans);return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/379668.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号