题解 p3818 小a和uim之大逃离 ii

using namespace std;
int qx[2000010], qy[2000010], qw[2000010], head, tail;
int dis[1010][1010][2], h, w, d, r;
char mp[1010][1010];
int fx[4] = {1, -1, 0, 0}, fy[4] = {0, 0, 1, -1};
int () {
    scanf("%d%d%d%d", &h, &w, &d, &r);
    for(int i = 0; i < h; i++) scanf("%s", mp[i]);
    memset(dis, -1, sizeof dis);
    head = tail = 0;
    qx[0] = qy[0] = qw[0] = 0;
    dis[0][0][0] = 0;
    if(mp[0][0] == '#') return puts("-1"), 0;
    while(head <= tail) {
        
        for(int i = 0; i < 4; i++) {
            int newx = qx[head] + fx[i], newy = qy[head] + fy[i];
            if(newx >= 0 && newx < h && newy >= 0 && newy < w && dis[newx][newy][qw[head]] == -1 && mp[newx][newy] == '.') {
                dis[newx][newy][qw[head]] = dis[qx[head]][qy[head]][qw[head]] + 1;
                tail++;
                qx[tail] = newx;
                qy[tail] = newy;
                qw[tail] = qw[head];
            }
        }
        int newx = qx[head] + d, newy = qy[head] + r;
        if(qw[head] == 0 && newx >= 0 && newx < h && newy >= 0 && newy < w && dis[newx][newy][1] == -1 && mp[newx][newy] == '.') {
            dis[newx][newy][1] = dis[qx[head]][qy[head]][qw[head]] + 1;
            tail++;
            qx[tail] = newx;
            qy[tail] = newy;
            qw[tail] = 1;
        }
        head++;
    }
    printf("%dn", (int)min((unsigned)dis[h - 1][w - 1][1], (unsigned)dis[h - 1][w - 1][0]));
    return 0;
}