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 }腾讯云开发者
