Language: C++

#include<iostream>
#include<queue>
#include<vector>
#include<complex>
#include<cmath>
using namespace std;
#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define pb         push_back
#define NODE(i,j,c)  ((i)*c+(j)+2)
#define ALL(C)      (C).begin(),(C).end()
typedef long long ll;
typedef complex<double> P;

const ll inf = (1LL)<<60;

enum{E=0,N=1,W=2,S=3};
enum{HOR=0,VER=1};//HOR- VER|
char dir[]={"NESW"};

ll check(ll t,int dir,int s,int n,int e){//need to take dir%2
  dir%=2;
  if (n+e==0)return 0;
  ll mod=n+e;
  ll tmp=t%mod;
  if (s==HOR){
    if (tmp <n){
      if (dir==HOR)return n-tmp;
      else if (dir==VER)return 0;
    }else {
      if (dir==HOR)return n+e-tmp;
      else if (dir==VER)return 0;
    }
  }else if (s == VER){
    if (tmp < e){
      if (dir==HOR)return 0;
      else if (dir==VER)return e-tmp;
    }else {
      if (dir==HOR)return e+n-tmp;
      else if (dir==VER)return 0;
    }
  }
  return -1;
}

class state{
public:
  int now,dir;ll cost;
  bool operator<(const state&a)const{
    return cost > a.cost;
  }
};

typedef struct{int to,dir;ll cost;}Edge;


const int node =100*100+2;
ll cost[node][4];
vector<Edge> edge[node];
int  es[node];
int  ns[node];
int  s[node];

ll dijkstra(int n){//src==0,dst==1
  rep(i,n)rep(j,4)cost[i][j]=inf;
  priority_queue<state> Q;
  rep(i,edge[0].size()){
    int nex=edge[0][i].to;
    int ned=edge[0][i].dir;
    cost[nex][ned]=edge[0][i].cost;
    cost[nex][ned]+=check(cost[nex][ned],ned,s[nex],ns[nex],es[nex]);
    Q.push((state){nex,ned,cost[nex][ned]});
  }

  while(!Q.empty()){
    state now = Q.top();Q.pop();
    if (cost[now.now][now.dir] != now.cost)continue;
    if (now.now == 1)return now.cost;
    //    cout << now.now <<" " << dir[now.dir] <<" " << now.cost << endl;

    rep(i,edge[now.now].size()){
      int nex=edge[now.now][i].to;
      int ned=edge[now.now][i].dir;
      ll  tcost=now.cost+edge[now.now][i].cost;
      //ll check(ll t,int dir,int s,int n,int e){//need to take dir%2
      //      cout << now.now <<" " << nex <<" " << check(tcost,ned,s[nex],ns[nex],es[nex])<<endl;
      tcost+=check(tcost,ned,s[nex],ns[nex],es[nex]);
      if (tcost < cost[nex][ned]){
	cost[nex][ned]=tcost;
	Q.push((state){nex,ned,tcost});
      }
    }
  }
  return -1;
}

bool isp(double x1,double y1,double x2,double y2,double x3,double y3){
  P a(x1,y1),b(x2,y2),c(x3,y3);
  return abs(a-c)+abs(b-c) < abs(a-b)+1e-10;
}

void setpos(int cur,int xs,int ys,vector<int> &x,vector<int> &y){
  int r=y.size(),c=x.size();
  rep(i,x.size()){
    if (xs == x[i]){
      int tmp=(int)(upper_bound(ALL(y),ys)-y.begin())-1;
      edge[cur].pb((Edge){NODE(tmp+1,i,c),N,y[tmp+1]-ys});
      edge[NODE(tmp+1,i,c)].pb((Edge){cur,S,y[tmp+1]-ys});
      edge[cur].pb((Edge){NODE(tmp,i,c)  ,S,ys-y[tmp]});
      edge[NODE(tmp,i,c)].pb((Edge){cur,N,ys-y[tmp]});
    }
  }

  rep(i,y.size()){
    if (ys == y[i]){
      int tmp=(int)(upper_bound(ALL(x),xs)-x.begin())-1;
      edge[cur].pb((Edge){NODE(i,tmp+1,c),E,x[tmp+1]-xs});
      edge[NODE(i,tmp+1,c)].pb((Edge){cur,W,x[tmp+1]-xs});

      edge[cur].pb((Edge){NODE(i,tmp,c  ),W,xs-x[tmp]});
      edge[NODE(i,tmp,c)].pb((Edge){cur  ,E,xs-x[tmp]});
    }
  }
}

ll issame(int a,int b,vector<int> &cor,vector<int>&c,int cd){
  bool isok=false;
  rep(i,c.size()){
    if (c[i] == cd)isok=true;
  }
  if (!isok)return -1;
  rep(i,cor.size()-1){
    if (cor[i] <= a && a <= cor[i+1] &&
	cor[i] <= b && b <= cor[i+1])return abs(a-b);
  }
  return -1;
}

main(){
  int r,c;
  while(cin>>r>>c && r){
    vector<int> x(c,0),y(r,0);
    REP(i,1,c)cin>>x[i],x[i]+=x[i-1];
    REP(i,1,r)cin>>y[i],y[i]+=y[i-1];
    rep(i,r*c+2)edge[i].clear();

    rep(i,r){
      rep(j,c){
	int cur=NODE(i,j,c),nex;
	ll dist;
	if (i){
	  nex=NODE(i-1,j,c);dist=y[i]-y[i-1];
	  edge[cur].pb((Edge){nex,S,dist});
	}
	if (i+1!=r){
	  nex=NODE(i+1,j,c);dist=y[i+1]-y[i];
	  edge[cur].pb((Edge){nex,N,dist});
	}
	if (j){
	  nex=NODE(i,j-1,c);dist=x[j]-x[j-1];
	  edge[cur].pb((Edge){nex,W,dist});
	}
	if (j+1!=c){
	  nex=NODE(i,j+1,c);dist=x[j+1]-x[j];
	  edge[cur].pb((Edge){nex,E,dist});
	}
      }
    }

    rep(i,r){
      rep(j,c)cin>>ns[NODE(i,j,c)]>>es[NODE(i,j,c)]>>s[NODE(i,j,c)];
    }

    int xs,ys,xd,yd;
    cin>>xs>>ys>>xd>>yd;
    setpos(0,xs,ys,x,y);
    setpos(1,xd,yd,x,y);
    if (xs==xd){
      ll tmp=issame(ys,yd,y,x,xs);
      if (tmp != -1){cout << tmp << endl;continue;}
    }else if (ys==yd){
      ll tmp=issame(xs,xd,x,y,ys);
      if (tmp != -1){cout << tmp << endl;continue;}
    }
    cout << dijkstra(r*c+2) << endl;

//      rep(i,x.size())cout << x[i]<<" ";cout <<endl;
//      rep(i,y.size())cout<<y[i]<<" ";cout << endl;
//      rep(i,r*c+2){
//        cout << "now ";
//        if (i == 0)cout <<0 <<"(" << xs <<"," << ys <<")";
//        else if (i == 1)cout << 1 <<"(" << xd <<"," << yd <<")";
//        else cout <<i <<"(" <<  x[(i-2)%c] <<"," << y[(i-2)/c] << ")";
//        cout << endl;
//        rep(j,edge[i].size()){
//  	cout << edge[i][j].to<<" " ;
//  	if (edge[i][j].to==0)cout << xs <<" " << ys <<" ";
//  	else if(edge[i][j].to == 1)cout <<xd <<" " << yd <<" ";
//  	else cout << "(" << x[(edge[i][j].to-2)%c] <<"," << y[(edge[i][j].to-2)/c] <<")";
//  	cout << edge[i][j].cost <<" " << dir[edge[i][j].dir] << endl;
//        }
//        cout << endl;
//      }

  }
  return false;
}

Compiler output:
a.cc: In function 'void setpos(int, int, int, std::vector<int>&, std::vector<int>&)':
a.cc:106:21: error: 'upper_bound' was not declared in this scope
  106 |       int tmp=(int)(upper_bound(ALL(y),ys)-y.begin())-1;
      |                     ^~~~~~~~~~~
a.cc:116:21: error: 'upper_bound' was not declared in this scope
  116 |       int tmp=(int)(upper_bound(ALL(x),xs)-x.begin())-1;
      |                     ^~~~~~~~~~~
a.cc: At global scope:
a.cc:139:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  139 | main(){
      | ^~~~