#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;idst)swap(src,dst); int sx,sy,tx,ty; sx = src%w; sy = src/w; tx = dst%w; ty = dst/w; if(sx==tx){ FOR(i,sy,ty){ if(lt[gp(sx,i)][1]!=gp(sx,i)){ i = lt[gp(sx,i)][1]/w; if(i>=ty)break; } g[sx+i*w] |= dir[1]; g[sx+(i+1)*w] |= dir[3]; lt[sx+i*w][1] = max(lt[sx+i*w][1],dst); } }else{ FOR(i,sx,tx){ if(lt[gp(i,sy)][0]!=gp(i,sy)){ i = lt[gp(i,sy)][0]%w; if(i>=tx)break; } g[sy*w+i] |= dir[0]; g[sy*w+i+1] |= dir[2]; lt[sy*w+i][0] = max(lt[sy*w+i][0],dst); } } } int main(){ // w,h<1e3 // |V| = wh < 1e6 // n < 1e3 // m < 1e3 // |E| = nm < 1e6 int n; cin>>w>>h>>n; if(w==1 && h==1){ cout<<0<>m; int bef; cin>>bef; REP(i,m){ int cur; cin>>cur; add_edge(bef,cur); bef = cur; } } queue Q; int s = 0; int t = w*h-1; Q.push(make_pair(0,0)); int res = -1; vector used(w*h,false); while(!Q.empty()){ pii P = Q.front(); Q.pop(); // int pos = P.second; int pos = P.first; if(used[pos])continue; used[pos] = true; // int wei = INF-P.first; int wei = P.second; int x = pos%w; int y = pos/w; // FOR(i,0,2){ // int dst = g[pos][i]; // int tx = x+dx[i]; // int ty = y+dy[i]; // int tpos = gp(tx,ty); // int cnt = 1; // while(0<=tx && tx= dst && !used[tpos]){ // if(tpos==t){ // cout<<(wei+1)<=w)continue; if(ty<0 || ty>=h)continue; int tpos = ty*w+tx; if(tpos<0 || tpos>=w*h)continue; if(used[tpos])continue; if(tpos == t){ cout<<(wei+1)<