RT，九个点MLE

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define min(a,b) a<b?a:b
const int maxh=1001+10;
const int maxr=1001+10;
const int INF=0x3f3f3f3f;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
int h,w,d,r,ans=INF;
int map[maxh][maxr];
bool vis[maxh][maxr];
struct node
{
  int x,y,step;
  bool ml;
};
queue <node> q;
bool check(int x,int y)
{
  if(x<1 || x>h || y<1 || y>w)  return false;
  if(map[x][y])  return false;
  return true;
}
void bfs()
{
  q.push((node){1,1,0,false});
  while(!q.empty())
  {
    node u=q.front();
    q.pop();
    if(u.step>ans)  continue;
    if(u.x==h && u.y==w)  ans=min(ans,u.step);
    if(!u.ml && check(u.x+d,u.y+r))  q.push((node){u.x+d,u.y+r,u.step+1,true});
    for(int i=0;i<4;i++)
    {
      int nx=u.x+dx[i];
      int ny=u.y+dy[i];
      if(check(nx,ny))
      {
        if(u.ml)  q.push((node){nx,ny,u.step+1,true});
        else  q.push((node){nx,ny,u.step+1,false});
      }
    }
  }
}

int main()
{
    scanf("%d%d%d%d",&h,&w,&d,&r);
    for(int i=1;i<=h;i++)
     for(int j=1;j<=w;j++)
     {
       char ch;
       cin>>ch;
       if(ch=='#')  map[i][j]=1;
     }
    bfs();
    if(ans==INF)  printf("-1");
    else  printf("%d",ans);
    return 0;
}