首页 > > 程序设计 > C/C++ >

P3818 小A和uim之大逃离 II

2018-06-17 22:19:10来源：未知阅读 ()

题目背景

话说上回……还是参见 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：

输入样例#2：

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

输出样例#2：

-1

输入样例#3：

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

输出样例#3：

说明

样例解释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 }