做网站市场价格合肥seo网站排名

1、题目类型：迷宫、BFS。

2、解题思路：（1）cin.getline()接收迷宫；（2）BFS搜索其开始位置 'S' 和其结束位置 'E' 并记录两者间的总步数、横向移动步数；（3）根据搜索答案判断其是否满足题意，满足输出结果。

3、注意事项：注意一定存在最短路径、找到符合题意答案即输出。

4、实现方法:

#include<iostream>
#include<queue>
#include<string>
using namespace std;

struct Point
{
int x,y;
int step;
int ver;
};

Point S,E;
string map[120];
char ch[120];
double L;
int n,m;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};

void Init()
{
int i,j;
 cin>>L>>n;
 m=120;
 cin.getline(ch,sizeof(ch));
for(i=0;i<n;i++)
 {
 map[i]="";
 {
 cin.getline(ch,sizeof(ch));
 map[i]=ch; 
if(m>map[i].length())
 m=map[i].length();
 }
 }
for(i=0;i<n;i++)
 {
for(j=0;j<map[i].length();j++)
 {
if(map[i][j]=='S')
 {
 S.x=i;
 S.y=j;
 }
if(map[i][j]=='E')
 {
 E.x=i;
 E.y=j;
 }
 }
 }
}

void Solve(int ca)
{
 queue<Point> Q;
int vis[120][120]={0};
int i,x,y,flag=0;
 S.ver=0;
 S.step=0;
 Q.push(S);
while(!Q.empty())
 {
 Point tmp=Q.front();
 Q.pop();

for(i=0;i<4;i++)
 {
 x=tmp.x+dir[i][0];
 y=tmp.y+dir[i][1];

if(x>=0 && x<n && y>=0 && y<m && !vis[x][y] && map[x][y]!='#')
 { 
 Point p;
if(map[x][y]=='E')
 {
if(i==0||i==2)
 p.ver=tmp.ver+1;
else
 p.ver=tmp.ver; 
 p.step=tmp.step+1; 
if(L<p.step-p.ver)
continue; 
double ans=L-p.step+p.ver; 
if(ans>=0)
 ans=ans/p.ver;
else
 ans=(-ans)/p.ver;
 ans*=100;
 printf("Case #%d: %.3lf%%\n",ca,ans);
return ; 
 }
 p.x=x;
 p.y=y;
 p.step=tmp.step+1;
if(i==0||i==2)
 p.ver=tmp.ver+1;
else
 p.ver=tmp.ver;
 Q.push(p);
 vis[x][y]=1;
 }
 } 
 }
}

int main()
{
int i,T; 
 cin>>T;
for(i=1;i<=T;i++)
 {
 Init();
 Solve(i);
 }
return 0;
}