#include #include using namespace std; int p[4]={1,0,-1,0},q[4]={0,1,0,-1}; char map[1010][1010]; int h,w,d,r; int x,y,z,n; bool bo1[1010][1010],bo2[1010][1010]; queueqx; queueqy; queuenum; queuebo; int main(){ cin>>h>>w>>d>>r; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin>>map[i][j]; qx.push(1); qy.push(1); num.push(0); bo.push(1); bo1[1][1]=1; while(!qx.empty()){ x=qx.front(); qx.pop(); y=qy.front(); qy.pop(); z=num.front(); num.pop(); n=bo.front(); bo.pop(); if(x==h&&y==w){ cout<<z<<endl; return 0; } for(int i=0;i<=3;i++){ if(x+p[i]>0&&y+q[i]>0&&map[x+p[i]][y+q[i]]=='.'){ if(bo1[x+p[i]][y+q[i]])continue; if(!n&&bo2[x+p[i]][y+q[i]])continue; qx.push(x+p[i]);qy.push(y+q[i]); num.push(z+1);bo.push(n); if(n)bo1[x+p[i]][y+q[i]]=1; else bo2[x+p[i]][y+q[i]]=1; } } if(n&&map[x+d][y+r]=='.'&&!bo1[x+d][y+r]&&!bo2[x+d][y+r]){ qx.push(x+d);qy.push(y+r); num.push(z+1);bo.push(0); bo2[x+d][y+r]=1; } } cout<<"-1"<<endl; return 0; }

#include<iostream>
#include<queue>
using namespace std;
int p[4]={1,0,-1,0},q[4]={0,1,0,-1};
char map[1010][1010];
int h,w,d,r;
int x,y,z,n;
bool bo1[1010][1010],bo2[1010][1010];
queue<int>qx;
queue<int>qy;
queue<int>num;
queue<bool>bo;
int main(){
	cin>>h>>w>>d>>r;
	for(int i=1;i<=h;i++)
		for(int j=1;j<=w;j++)
			cin>>map[i][j];
	qx.push(1);
	qy.push(1);
	num.push(0);
	bo.push(1);
	bo1[1][1]=1;
	while(!qx.empty()){
		x=qx.front();
		qx.pop();
		y=qy.front();
		qy.pop();
		z=num.front();
		num.pop();
		n=bo.front();
		bo.pop();
		if(x==h&&y==w){
			cout<<z<<endl;
			return 0;
		}
		for(int i=0;i<=3;i++){
			if(x+p[i]>0&&y+q[i]>0&&map[x+p[i]][y+q[i]]=='.'){
				if(bo1[x+p[i]][y+q[i]])continue;
				if(!n&&bo2[x+p[i]][y+q[i]])continue;
				qx.push(x+p[i]);qy.push(y+q[i]);
				num.push(z+1);bo.push(n);
				if(n)bo1[x+p[i]][y+q[i]]=1;
				else bo2[x+p[i]][y+q[i]]=1;
			}
		}
		if(n&&map[x+d][y+r]=='.'&&!bo1[x+d][y+r]&&!bo2[x+d][y+r]){
			qx.push(x+d);qy.push(y+r);
			num.push(z+1);bo.push(0);
			bo2[x+d][y+r]=1;
		}
	}
	cout<<"-1"<<endl;
	return 0;
}