Proficient.
Put your skills to the test.

Problem summary

At time t=1,2,..., either stay in place or jump exactly t cells horizontally or vertically. Landing must be on an empty in-bounds cell, but jumping over blocked cells is allowed. Find the earliest arrival from top left to bottom right.

Constraints

1 ≤ N*M ≤ 1000000; 1 ≤ N,M ≤ 1000000; N*M>1; the two corner cells are empty.

Worked example

An independently prepared example for this explanation.

1 6
..#...

4

Solution analysis

1. If a cell is reached at time d, waiting permits a jump to any same-row or same-column cell at distance t>d, arriving at time t. Earlier arrival always dominates later arrival at the same cell, so Dijkstra’s settlement principle applies. The challenge is processing these implicit long-range edges.
2. Each settled cell (r,c) offers four intervals. To its left, columns j<c−d have candidate arrival c−j; to its right, j>c+d have arrival j−c; the vertical formulas are analogous. Maintain four segment trees for these four linear forms, using row-major order for horizontal intervals and column-major order for vertical intervals.
3. In a tree, each active leaf has a fixed base coordinate j or −j. An interval offer applies candidate=min(candidate,base+constant). A node stores the least active base, least candidate, and smallest pending constant. This supports offers and deletion of a settled cell in logarithmic time. Repeatedly extract the globally smallest root candidate across the four trees. In the example, cell two is reached at time one, waits through times two and three, then jumps four cells to the goal at time four.

Why it works

Any feasible route reaching a cell later can be replaced by an earlier route followed by waiting, so only earliest arrival matters. From a settled time d, the four offered intervals are exactly the legal future jump destinations, each with its earliest possible arrival equal to its geometric distance. Node minimum updates are exact because min over active leaves of base+constant is nodeMinBase+constant, and pending constants compose by minimum. The global minimum unsettled candidate is therefore the next Dijkstra distance. Removing settled cells preserves the invariant and the first goal settlement is optimal; an infinite minimum means no further reachable cell exists.

Watch out. Require jump distance strictly greater than the source arrival time. Blocked cells are absent leaves, but may be jumped over. Delete a settled cell in all four orientations to avoid settling it repeatedly.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
// Algorithm: If a cell is reached at time d, waiting permits a jump to any same-row or
// same-column cell at distance t>d, arriving at time t.
using namespace std;
const int INFINITY_TIME=1000000000;
struct OfferTree{
    int length;
    vector<int>base,best,lazy;
    OfferTree(int count,const vector<int>&coordinates)
        :length(count),base(2*count,INFINITY_TIME),best(2*count,INFINITY_TIME),
            lazy(2*count,INFINITY_TIME){
        build(0,0,length-1,coordinates);
    }
    void build(int node,int left,int right,const vector<int>&coordinates){
        if(left==right){
            base[node]=coordinates[left];
            return;
        }
        int middle=(left+right)/2;
        int other=node+2*(middle-left+1);
        build(node+1,left,middle,coordinates);
        build(other,middle+1,right,coordinates);
        base[node]=min(base[node+1],base[other]);
    }
    void apply(int node,int constant){
        if(base[node]<INFINITY_TIME){
            best[node]=min(best[node],base[node]+constant);
            lazy[node]=min(lazy[node],constant);
        }
    }
    void push(int node,int other){
        if(lazy[node]!=INFINITY_TIME){
            apply(node+1,lazy[node]);
            apply(other,lazy[node]);
            lazy[node]=INFINITY_TIME;
        }
    }
    void pull(int node,int other){
        base[node]=min(base[node+1],base[other]);
        best[node]=min(best[node+1],best[other]);
    }
    void offer(int node,int left,int right,int first,int last,int constant){
        if(last<left||right<first){
            return;
        }
        if(first<=left&&right<=last){
            apply(node,constant);
            return;
        }
        int middle=(left+right)/2;
        int other=node+2*(middle-left+1);
        push(node,other);
        offer(node+1,left,middle,first,last,constant);
        offer(other,middle+1,right,first,last,constant);
        pull(node,other);
    }
    void offer(int left,int right,int constant){
        if(left<=right){
            offer(0,0,length-1,left,right,constant);
        }
    }
    int minimumPosition(int node,int left,int right){
        if(left==right){
            return left;
        }
        int middle=(left+right)/2;
        int other=node+2*(middle-left+1);
        push(node,other);
        if(best[node+1]<=best[other]){
            return minimumPosition(node+1,left,middle);
        }
        return minimumPosition(other,middle+1,right);
    }
    void remove(int node,int left,int right,int position){
        if(left==right){
            base[node]=best[node]=lazy[node]=INFINITY_TIME;
            return;
        }
        int middle=(left+right)/2;
        int other=node+2*(middle-left+1);
        push(node,other);
        if(position<=middle){
            remove(node+1,left,middle,position);
        }
        else{
            remove(other,middle+1,right,position);
        }
        pull(node,other);
    }
    void remove(int position){
        remove(0,0,length-1,position);
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows,columns;
    cin>>rows>>columns;
    vector<string>grid(rows);
    for(auto&row:grid){
        cin>>row;
    }
    int cells=rows*columns;
    vector<OfferTree>trees;
    trees.reserve(4);
    for(int orientation=0;orientation<4;++orientation){
        vector<int>coordinates(cells,INFINITY_TIME);
        for(int row=0;row<rows;++row){
            for(int column=0;column<columns;++column){
                if(grid[row][column]=='#'){
                    continue;
                }
                int index=orientation<2?row*columns+column:column*rows+row;
                int coordinate=orientation<2?column:row;
                coordinates[index]=orientation%2==0?coordinate:-coordinate;
            }
        }
        trees.emplace_back(cells,coordinates);
    }
    int row=0,column=0,time=0;
    while(true){
        if(row==rows-1&&column==columns-1){
            cout<<time<<'\n';
            return 0;
        }
        int horizontal=row*columns+column;
        int vertical=column*rows+row;
        trees[0].remove(horizontal);
        trees[1].remove(horizontal);
        trees[2].remove(vertical);
        trees[3].remove(vertical);
        if(column+time+1<columns){
            trees[0].offer(horizontal+time+1,row*columns+columns-1,-column);
        }
        if(column-time-1>=0){
            trees[1].offer(row*columns,horizontal-time-1,column);
        }
        if(row+time+1<rows){
            trees[2].offer(vertical+time+1,column*rows+rows-1,-row);
        }
        if(row-time-1>=0){
            trees[3].offer(column*rows,vertical-time-1,row);
        }
        int chosen=0;
        for(int i=1;i<4;++i){
            if(trees[i].best[0]<trees[chosen].best[0]){
                chosen=i;
            }
        }
        time=trees[chosen].best[0];
        if(time==INFINITY_TIME){
            cout<<"-1\n";
            return 0;
        }
        int index=trees[chosen].minimumPosition(0,0,cells-1);
        if(chosen<2){
            row=index/columns;
            column=index%columns;
        }
        else{
            row=index%rows;
            column=index/rows;
        }
    }
}