实验作业

2019-10-25 06:26:30来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

实验作业

★实验任务

NC一天要去走一个迷宫,迷宫是由一个 R*C的网格表示。迷宫只有一个出口和一个入口,这个大家都知道。迷宫的出口在第一行,出口在最底行。他想知道走出迷宫的最短时间。这是一个很简单的问题,至于你信不信,反正我是信了。

★数据输入

输入第一行包括四个正整数 R,C,ENT,EXIT(2<=R<=200,2<=C<=200),表示 R 行,C列,入口在第ENT列,出口在EXIT列。

接下 2*R-1行,第2*i行有 C-1个数,第j个数表示网格 g[i][j] 与 g[i][j+1] 之间有墙壁。第 2*i+1 行有 C 个数,第 j 个数表示网格 g[i][j] 和 g[i+1][j] 之间有墙壁。‘0'表示没有墙壁,‘1’表示两个位置之间有墙壁。

★数据输出

如有有路径走出,则输出最短的步数,否则输出“No Way”(没有引号)。


#include<iostream> #include<queue> using namespace std; bool vis[203][203]; struct node{ int x,y,step; }; int n,m,s,e; int dx[5]={1,-1,0,0}; int dy[5]={0,0,1,-1}; int row[202][202][202]; int col[202][202][202]; int bfs() { queue<node>q; node p; p.x=1;p.y=s;p.step=1; q.push(p); vis[p.x][p.y]=1; while(q.size()) { node top=q.front(); q.pop(); int tx=top.x; int ty=top.y; int ts=top.step; if(tx==n&&ty==e) { return (ts+1); } for(int i=0;i<=1;i++)//列走 { int xx=tx+dx[i]; int yy=ty+dy[i]; int ss=ts+1; if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1||col[tx][xx][yy]==1) continue; else { node tmp; tmp.x=xx;tmp.y=yy;tmp.step=ss; q.push(tmp); vis[xx][yy]=1; } } for(int i=2;i<=3;i++)//行走 { int xx=tx+dx[i]; int yy=ty+dy[i]; int ss=ts+1; if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1||row[xx][ty][yy]==1) continue; else { node tmp; tmp.x=xx;tmp.y=yy;tmp.step=ss; q.push(tmp); vis[xx][yy]=1; } } } return 0; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>s>>e; int x; for(int i=1;i<=n;i++) { for(int j=1;j<=m-1;j++) { cin>>x;//第i行第j列到第j+1列能不能走 row[i][j][j+1]=row[i][j+1][j]=x; } if(i!=n) for(int j=1;j<=m;j++) { cin>>x;//第i列到第i+1列第j个格子能不能走 col[i][i+1][j]=col[i+1][i][j]=x; } } int k=bfs(); if(k) cout<<k; else cout<<"No Way"; }
成长从现在开始

  


原文链接:https://www.cnblogs.com/dronw/p/11725478.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:10.22 学习总结

下一篇:P2995 [USACO10NOV]牛的照片(树状数组,逆序对)