P3818 小A和uim之大逃离 II

题目背景

话说上回……还是参见 https://www.luogu.org/problem/show?pid=1373 吧

小a和uim再次来到雨林中探险。突然一阵南风吹来,一片乌云从南部天边急涌过来,还伴着一道道闪电,一阵阵雷声。刹那间,狂风大作,乌云布满了天空,紧接着豆大的雨点从天空中打落下来,只见前方出现了一个牛头马面的怪物,低沉着声音说:“呵呵,既然你们来到这,两个都别活了!”。小a和他的小伙伴再次惊呆了!

题目描述

瞬间,地面上出现了一个H行W列的巨幅矩阵,矩阵的每个格子上要么是空地‘.’或者障碍'#'。

他们起点在(1,1),要逃往(H,W)的出口。他们可以一次向上下左右移动一格,这个算一步操作。不过他们还保留着上次冒险时收集的魔液,一口气喝掉后可以瞬移到相对自己位置的(D,R)向量;也就是说,原来的位置是(x,y),然后新的位置是(x+D,y+R),这个也算一步操作,不过他们仅能至多进行一次这种操作(当然可以不喝魔液)。

这个地方是个是非之地。所以他们希望知道最小能有几步操作可以离开这个鬼地方。不过他们可能逃不出这个鬼地方,遇到这种情况,只能等死,别无他法。

输入输出格式

输入格式:

第一行个整数,H W D R,意义在描述已经说明。

接下来H行,每行长度是W,仅有'.'或者'#'的字符串。

输出格式:

请输出一个整数表示最小的逃出操作次数。如果他们逃不出来,就输出-1。

输入输出样例

输入样例#1:

3 6 2 1
...#..
..##..
..#...

输出样例#1:

5

输入样例#2:

3 7 2 1
..#..#.
.##.##.
.#..#..

输出样例#2:

-1

输入样例#3:

6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.

输出样例#3:

21

说明

样例解释1

(1,1)→(1,2)→(1,3)→喝(3,4)→(3,5)→(3,6)

样例解释2

因为只有一瓶魔液所以他们没办法逃出来

样例解释3

D和R还可以是0或者负数。

数据范围与约定

40%的测试数据2<=H,W<=5

70%的测试数据2<=H,W<=100

100%的测试数据2<=H,W<=1000,|D|<H,|R|<W

其实这题大可不必建边跑最短路什么的。

我们可以用一个vis[i][j][0/1]数组来记录状态。

0表示是通过走路的方式到达的这个点,

1表示通过魔法的方式走的到这个点。

还有一个很坑的地方就是vis开小了会RE第2个点,开大了会RE第7个点,

莫名其妙

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 #include<algorithm>
  7 #define lli long long int 
  8 using namespace std;
  9 void read(int &n)
 10 {
 11     char c='+';int x=0;bool flag=0;
 12     while(c<'0'||c>'9')
 13     {c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9')
 15     {x=x*10+(c-48);c=getchar();}
 16     flag==1?n=-x:n=x;
 17 }
 18 int n,m;
 19 int mox,moy;
 20 int map[2501][2501];
 21 bool vis[2501][2101][3];
 22 int xx[5]={-1,+1,0,0};
 23 int yy[5]={0,0,-1,+1};
 24 struct node
 25 {
 26     int x,y,step;
 27     bool flag;// 是否喝了药水、 
 28 }now,nxt;
 29 void  BFS()
 30 {
 31     queue<node>q;
 32     vis[1][1][0]=1;
 33     //vis[bgx][bgy][1]=1;
 34     now.x=1;
 35     now.y=1;
 36     now.flag=0;
 37     now.step=0;
 38     q.push(now);
 39     bool end=0;
 40     while(q.size()!=0)
 41     {
 42         node p=q.front();
 43         q.pop();
 44         if(p.x<0||p.y<0||p.x>n||p.y>m)
 45             continue;
 46         for(int i=0;i<4;i++)
 47         {
 48             int wx=xx[i]+p.x;
 49             int wy=yy[i]+p.y;
 50             if(map[wx][wy]==1&&wx>0&&wy>0&&wx<=n&&wy<=m)
 51             {
 52                 if(vis[wx][wy][p.flag]==0)
 53                 {
 54                 vis[wx][wy][p.flag]=1;
 55                 node w;
 56                 w.x=wx;
 57                 w.y=wy;
 58                 w.step=p.step+1;
 59                 w.flag=p.flag;
 60                 if(wx==n&&wy==m)
 61                 {
 62                     printf("%d",w.step);
 63                     return ;
 64                 }
 65                 q.push(w);    
 66                 }
 67                 
 68             }
 69         }
 70         if(p.flag==0)
 71         {
 72             int wx=p.x+mox;
 73             int wy=p.y+moy;    
 74             if(map[wx][wy]==1&&wx>0&&wy>0&&wx<=n&&wy<=m)
 75             {
 76                 if(vis[wx][wy][1]==0)
 77                 {
 78                     vis[wx][wy][1]=1;
 79                     node w;
 80                     w.x=wx;
 81                     w.y=wy;
 82                     w.step=p.step+1;
 83                     w.flag=1;
 84                     if(wx==n&&wy==m)
 85                     {
 86                         printf("%d",w.step);
 87                         return ;
 88                     }
 89                     q.push(w);    
 90                 }
 91             }
 92         }
 93     }
 94         printf("-1");
 95 }
 96 int main()
 97 {
 98     //ios::sync_with_stdio(false);
 99     cin>>n>>m>>mox>>moy;
100     for(int i=1;i<=n;i++)
101     {
102         for(int j=1;j<=m;j++)
103         {
104             char p;
105             cin>>p;
106             if(p=='.') map[i][j]=1;// 可以通过
107             else 
108             if(p=='#') map[i][j]=2;// 不能通过    
109         }
110     }
111     BFS();
112     return 0;
113 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏西枫里博客

Python学习笔记十一(递归)

本次学习先回顾了前两天的lambda表达式,使用lambda表达式创建匿名函数。接着学习本次课程的内容:Python的递归。什么是递归,程序调用自身的编程方法叫...

9220
来自专栏机器学习入门

POJ 刷题系列:1753. Flip Game

POJ 刷题系列:1753. Flip Game 传送门:POJ 1753. Filp Game 题意: 一个4*4的矩阵,每一格要么是白色,要么是黑色。现在...

29660
来自专栏海天一树

NOIP 2018普及组初赛C/C++答案详解

1 D 打印机是把电脑里的资料打印到纸上,所以是输出设备。 扫描仪、键盘和鼠标都是往电脑里输入东西,是输入设备。

31430
来自专栏AI科技大本营的专栏

送书 | 跟我一起学《流畅的Python》

本文引自图灵新书《流畅的Python》的第一章——Python数据模型。本书由奋战在Python开发一线近20年的Luciano Ramalho执笔,Victo...

43640
来自专栏移动端开发

快速排序OC、Swift版源码

前言: 你要问我学学算法在工作当中有什么用,说实话,当达不到那个地步的时候,可能我们不能直接的感觉到它的用处!你就抱着这样一个心态,当一些APP中涉及到算法...

25780
来自专栏数据结构与算法

群论入门

这东西一时半会儿写不完。。。 群 定义集合 ,*为集合G上的二元运算 当集合G在运算*之下满足一下性质时,我们称集合G在运算*之下是一个群,简称G是群 封闭性...

38350
来自专栏码云1024

c++ 虚继承

34570
来自专栏小樱的经验随笔

BZOJ 3670: [Noi2014]动物园【KMP变形 】

3670: [Noi2014]动物园 Time Limit: 10 Sec  Memory Limit: 512 MB Submit: 2738  Solve...

37170
来自专栏owent

不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

7410
来自专栏数据结构与算法

P1774 最接近神的人_NOI导刊2010提高(02)

题目描述 破解了符文之语,小FF开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“...

28360

扫码关注云+社区

领取腾讯云代金券