题目背景
话说上回……还是参见 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。
输入输出样例
3 6 2 1
...#..
..##..
..#...
5
3 7 2 1
..#..#.
.##.##.
.#..#..
-1
6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.
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
思路：
做过一遍，但这次只得了40分。TLE。
加了vis数组就过了。所以以后不能偷懒。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
const int N=;
int H,W,D,R;
char map[N][N];
int ans[][N][N];
bool vis[][N][N];
struct node{
int x;int y;
int step;
bool is=;
};
int dx[]={,-,,},dy[]={,,,-};
queue<node>q;
const int INF=1e8;
int tot=INF;
void bfs()
{
for(int i=;i<=H;i++)
for(int j=;j<=W;j++)
ans[][i][j]=ans[][i][j]=INF;
node O,to;int x,y;
O.x=,O.y=;O.step=;O.is=;
q.push(O);
ans[][][]=ans[][][]=;
O.is=;
q.push(O);
vis[][][]=vis[][][]=;
while(!q.empty())
{
O=q.front();q.pop();
if(O.x==H&&O.y==W) return ;
for(int i=;i<=;i++)
{
x=O.x+dx[i];y=O.y+dy[i];
if(x<||x>H||y<||y>W) continue;
if(O.step+<=ans[O.is][x][y]&&map[x][y]=='.')
{
to.x=x,to.y=y,to.step=O.step+,to.is=O.is;
ans[O.is][x][y]=O.step+;
if(!vis[O.is][x][y])
q.push(to),vis[O.is][x][y]=;
}
}
if(!O.is)
{
x=O.x+D;y=O.y+R;
if(x<||x>H||y<||y>W) continue;
if(O.step+<=ans[][x][y]&&map[x][y]=='.')
{
to.x=x,to.y=y,to.step=O.step+,to.is=;
ans[][x][y]=O.step+;
if(!vis[][x][y])
q.push(to),vis[][x][y]=;
}
}
}
} int main()
{ scanf("%d%d%d%d",&H,&W,&D,&R);
for(int i=;i<=H;i++)
for(int j=;j<=W;j++)
cin>>map[i][j];
bfs();
if(ans[][H][W])
tot=min(tot,ans[][H][W]);
if(ans[][H][W])
tot=min(tot,ans[][H][W]);
if(tot!=INF)
{
cout<<tot;
return ;
}
cout<<-;
return ;
}