3344 迷宫

 时间限制: 1 s
 空间限制: 32000 KB
 题目等级 : 黄金 Gold
 
 
 
题目描述 Description

小刚在迷宫内,他需要从A点出发,按顺序经过B,C,D……,到达最后一个点,再回到A点。迷宫内有些障碍,问至少走几步。

输入描述 Input Description

第一行有三个数n,m表示迷宫有n行,m列。

第2行到第n+1行,每行m个字符,可能是’A’..’Z’,’2’,’0’ 其中,2表示障碍,0表示可以走。’A’..’Z’也可以走。

输出描述 Output Description

至少走几步可以按规定走完,如果不行,输出“Impossible”

样例输入 Sample Input

5 5

A002B

022C0

000D0

00222

0000E

样例输出 Sample Output

26

数据范围及提示 Data Size & Hint

0%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“B”。

30%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“G”。

50%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“Z”。

10%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“B”。

30%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“G”。

100%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“Z”。

bfs

以A为起点以B为终点,以B为起点以C为终点、、、以此类推,跑sum遍bfs找出每一个点到它下一个点的最小值,然后累加就可以了。

不要忘了判断没有路的情况

#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 210
using namespace std;
char ch;
bool flag;
int dis[N][N],map[N][N];
int n,m,sx,sy,ex,ey,sum,ans;
]={,,,-},yy[]={,-,,};
int read()
{
    ,f=; char ch=getchar();
    ') ch=getchar();
    +ch-'; ch=getchar();}
    return x*f;
}
struct Node
{
    int x,y;
}node[],que;
queue<Node>q;
void bfs(int sx,int sy)
{
    while(!q.empty()) q.pop();
     memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[sx][sy]=;
    que.x=sx,que.y=sy,q.push(que);
    while(!q.empty())
    {
        Node p=q.front();q.pop();
        if(p.x==ex&&p.y==ey) {ans+=dis[ex][ey]; return ;}
        ;i<;i++)
        {
            int fx=p.x+xx[i],fy=p.y+yy[i];
            ||fy<||fx>n||fy>m||!map[fx][fy]) continue;
            ) continue;
            dis[fx][fy]=dis[p.x][p.y]+;
            que.x=fx,que.y=fy;
            q.push(que);
        }
    }
    flag=true;
}
int main()
{
    n=read(),m=read();
    ;i<=n;i++)
     ;j<=m;j++)
     {
         cin>>ch;
         ;
         ;
         if(ch>='A'&&ch<='Z')
         {
             sx=ch-;
             sum=max(sx,sum);
             node[sx].x=i;
             node[sx].y=j;
         }
      }
    ;i<=sum;i++)
    {
        sx=node[i].x,sy=node[i].y;
        if(i==sum)
         ex=node[].x,ey=node[].y;
        else
         ex=node[i+].x,ey=node[i+].y;
        bfs(sx,sy);
    }
    if(flag) printf("Impossible");
    else printf("%d",ans);
    ;
}

最新文章

  1. frame和bounds
  2. PHP最简单的后门,且难查,不报毒!
  3. &lt;&lt;Exceptional C++&gt;&gt; notes
  4. Debian deb源方法升级PHP软件包
  5. isArray polyfill
  6. `cocos2dx非完整` 开始自己的FW模块
  7. 小生经验贴 --- adapter的数据更新
  8. PHP中的urlencode和urldecode的理解
  9. Tornado基本使用
  10. c语言统计字符数(判断a-z哪个字符出现次数最多)
  11. centos ios镜像文件 安装详细
  12. 团队作业4——第一次项目冲刺(Alpha版本)第一天+第二天+第三天+第四天+第五天+第六天+第七天
  13. DNS查询相关
  14. 谈谈ISCSI\NAS\SAN及SAS之间的区别及优缺点--待补充
  15. 【机器学习】SKlearn + XGBoost 预测 Titanic 乘客幸存
  16. .Net转Java.08.format
  17. python写web服务器
  18. 1123.(重、错)Is It a Complete AVL Tree
  19. SharePoint 2013 workflows stop working (Failed on started.)
  20. 傻瓜式搭建php+nginx+mysql服务器环境

热门文章

  1. ccf 201712-3 Crontab(Python实现)
  2. 购物车小程序(while循环,列表)
  3. leetcode-25-exercise_string&amp;array
  4. UVa - 1592 Database(STL,优化)
  5. MySQL配置允许远程登录
  6. bash数组操作-定义/初始化/赋值…
  7. Flask-用户角色及权限
  8. django_orm操作
  9. String的getBytes()方法
  10. Selenium WebDriver- 操作 IFrame 中的页面元素