#include<cstdio> #include<queue> const int MAXN=1000+5; struct data{int x,y,step;bool drink;}; bool map[MAXN][MAXN],vis[MAXN][MAXN][2];int n,m;char inp[MAXN]; int xd[5]={-1,1,0,0,0},yd[5]={0,0,-1,1,0}; std::queue<data>que; int BFS() { data tmp,temp; tmp.x=1;tmp.y=1;tmp.step=0;tmp.drink=0; vis[1][1][0]=1;que.push(tmp); while(!que.empty()) { temp=que.front();que.pop(); for(int i=0;i<5;i++) { if(i==4 && temp.drink) continue; tmp=temp; tmp.x+=xd[i];tmp.y+=yd[i];tmp.step++; if(i==4) tmp.drink=1; if(vis[tmp.x][tmp.y][tmp.drink] || map[tmp.x][tmp.y] || tmp.x<1 || tmp.y<1 || tmp.x>n || tmp.y>m) continue; if(tmp.x==n && tmp.y==m) return tmp.step; que.push(tmp); vis[tmp.x][tmp.y][tmp.drink]=1; } } return -1; } int main() { scanf("%d %d %d %d",&n,&m,&xd[4],&yd[4]); if(n==1 && m==1) { printf("0"); return 0; } for(int i=1;i<=n;i++) { scanf("%s",inp+1); for(int j=1;j<=m;j++) map[i][j]=(inp[j]=='#'); } printf("%d",BFS()); return 0; }
|