#define TEMPLATE_VERSION "v0.2 06/03/2019"
#include <bits/stdc++.h>
#define MOD (1000000007LL)
#define INF (1000000)
#define LINF (LLONG_MAX)
#define TAM (2019)
#define LL long long int
#define ULL unsigned long long int
#define LD long double
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define si set<int>
#define qi queue<int>
#define sti stack<int>
#define vLL vector<LL>
#define pqi priority_queue<int>
#define pii pair<int, int>
#define vii vector<pii>
#define vvi vector<vi>
#define vvii vector<vii>
#define vs vector<string>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define EPS 1e-9
#define loop( n ) for(int i=0; i<n; i++)
#define LOOP(k,n) for(int i=k; i<n; i++)
#define POOL(k,n) for(int i=k; i>=n; i--)
#define FIND(v, value) find(v.begin(), v.end(), value)
#define SORT( v ) sort(v.begin(), v.end())
#define SORTC(v, comp) sort(v.begin(), v.end(), comp)
#define WW( x ) cout<<#x<<" = "<<(x)<<"\n";
#define endl '\n'
using namespace std;
vs matriz;
vi pontcomp, minx, miny, maxx, maxy;
vvi comp;
int X, Y, qtde_customers, qtde_offices;
void print(){
loop(X)
cout << matriz[i] << endl;
}
struct Customer{
int x, y, pontos, componente;
Customer(int a, int b, int c){
x = a;
y = b;
pontos = c;
componente = 0;
}
};
vector<Customer> customers;
int peso(pii pos){
char op = matriz[pos.f][pos.s];
if(op=='#') return INF;
if(op=='~') return 800;
if(op=='*') return 200;
if(op=='X') return 120;
if(op=='_') return 100;
if(op=='H') return 70;
if(op=='T') return 50;
}
pair<int, string> dijkstra (pii origem, pii destino){
int dist[TAM][TAM];
char prev[TAM][TAM];
for(int i=0; i<TAM; i++)
for(int j=0; j<TAM; j++)
{
dist[i][j] = INF;
prev[i][j] = 'X';
}
set< pair<int, pii> > fila;
fila.insert(mp(0, origem));
dist[origem.f][origem.s] = 0;
while(!fila.empty()){
cout << fila.begin()->second.first << " " << fila.begin()->s.s << "\n";
pii vertice = fila.begin()->second;
int distancia = dist[vertice.f][vertice.s];
int pes = peso(vertice);
fila.erase(*fila.begin());
int moves_x[] = {0, 0, 1, -1};
int moves_y[] = {1, -1, 0, 0};
char dir[] = {'R', 'L', 'D', 'U'};
for(int i=0; i<4; i++){
int atualX = moves_x[i]+vertice.f;
int atualY = moves_y[i]+vertice.s;
if(atualX>=0 and atualX<X and atualY>=0 and atualY<Y){
if(dist[atualX][atualY] > distancia + pes){
dist[atualX][atualY] = distancia + pes;
prev[atualX][atualY] = dir[i];
fila.insert(mp(dist[atualX][atualY], mp(atualX, atualY)));
}
}
}
}
string s;
pii cur = destino;
while (cur != origem)
{
s += prev[cur.f][cur.s];
if (prev[cur.f][cur.s] == 'U')
cur.f++;
else if (prev[cur.f][cur.s] == 'D')
cur.f--;
else if (prev[cur.f][cur.s] == 'R')
cur.s--;
else if (prev[cur.f][cur.s] == 'L')
cur.s++;
else
{
s += 'X';
break;
}
}
string s2 (s.rbegin(), s.rend());
return mp(dist[destino.f][destino.s], s2);
}
bool dfs (int x, int y, int c)
{
if (x < 0 or x >= X or y < 0 or y >= Y or matriz[x][y] == '#' or comp[x][y] > 0)
return false;
comp[x][y] = c;
dfs(x - 1, y, c);
dfs(x, y - 1, c);
dfs(x + 1, y, c);
dfs(x, y + 1, c);
return true;
}
int init_comp ()
{
vi aux (Y, 0);
comp.assign(X, aux);
int c = 1;
for (int i = 0; i < X; i++)
for (int j = 0; j < Y; j++)
if (dfs(i, j, c))
c++;
pontcomp.assign(c, 0);
for (int i = 0; i < qtde_customers; i++)
{
pontcomp[comp[customers[i].x][customers[i].y]] += customers[i].pontos;
customers[i].componente = comp[customers[i].x][customers[i].y];
}
minx.assign(c, TAM);
miny.assign(c, TAM);
maxx.assign(c, -1);
maxy.assign(c, -1);
for (int i = 0; i < X; i++)
for (int j = 0; j < Y; j++)
{
minx[comp[i][j]] = min(minx[comp[i][j]], i);
miny[comp[i][j]] = min(miny[comp[i][j]], j);
maxx[comp[i][j]] = max(maxx[comp[i][j]], i);
maxy[comp[i][j]] = max(maxy[comp[i][j]], j);
}
int cont = 0;
for (int i : pontcomp)
if (i > 0)
cont++;
return cont;
}
/*
pii binary_search (int c)
{
int minX = minx[c];
int minY = miny[c];
int maxY = maxy[c];
int maxX = maxx[c];
pii pos = mp((minX+maxX)/2, (minY+maxY)/2);
while(peso(pos)!=INF){
}
return pos;
}*/
int main () {
ios_base::sync_with_stdio(false);
cin >> Y >> X >> qtde_customers >> qtde_offices;
loop(qtde_customers){
int a, b, c;
cin >> a >> b >> c;
customers.pb(Customer(b, a, c));
}
loop(X){
string a;
cin >> a;
matriz.pb(a);
}
cout << init_comp() << endl;
print();
int px, py, qx, qy;
while (cin >> px >> py >> qx >> qy)
{
auto p = dijkstra(mp(px, py), mp(qx, qy));
cout << p.f << " " << p.s << "\n";
}
return 0;
}
I2RlZmluZSBURU1QTEFURV9WRVJTSU9OICJ2MC4yIDA2LzAzLzIwMTkiCiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKI2RlZmluZSBNT0QgKDEwMDAwMDAwMDdMTCkKI2RlZmluZSBJTkYgKDEwMDAwMDApCiNkZWZpbmUgTElORiAoTExPTkdfTUFYKQojZGVmaW5lIFRBTSAoMjAxOSkKI2RlZmluZSBMTCBsb25nIGxvbmcgaW50IAojZGVmaW5lIFVMTCB1bnNpZ25lZCBsb25nIGxvbmcgaW50CiNkZWZpbmUgTEQgbG9uZyBkb3VibGUKI2RlZmluZSB2aSB2ZWN0b3I8aW50PgojZGVmaW5lIHZiIHZlY3Rvcjxib29sPgojZGVmaW5lIHZzIHZlY3RvcjxzdHJpbmc+CiNkZWZpbmUgc2kgc2V0PGludD4KI2RlZmluZSBxaSBxdWV1ZTxpbnQ+CiNkZWZpbmUgc3RpIHN0YWNrPGludD4KI2RlZmluZSB2TEwgdmVjdG9yPExMPgojZGVmaW5lIHBxaSBwcmlvcml0eV9xdWV1ZTxpbnQ+CiNkZWZpbmUgcGlpIHBhaXI8aW50LCBpbnQ+IAojZGVmaW5lIHZpaSB2ZWN0b3I8cGlpPgojZGVmaW5lIHZ2aSB2ZWN0b3I8dmk+IAojZGVmaW5lIHZ2aWkgdmVjdG9yPHZpaT4KI2RlZmluZSB2cyB2ZWN0b3I8c3RyaW5nPgojZGVmaW5lIHBiIHB1c2hfYmFjawojZGVmaW5lIG1wIG1ha2VfcGFpcgojZGVmaW5lIGYgZmlyc3QKI2RlZmluZSBzIHNlY29uZAojZGVmaW5lIEVQUyAxZS05CiNkZWZpbmUgbG9vcCggbiApIGZvcihpbnQgaT0wOyBpPG47IGkrKykKI2RlZmluZSBMT09QKGssbikgZm9yKGludCBpPWs7IGk8bjsgaSsrKQojZGVmaW5lIFBPT0woayxuKSBmb3IoaW50IGk9azsgaT49bjsgaS0tKQojZGVmaW5lIEZJTkQodiwgdmFsdWUpIGZpbmQodi5iZWdpbigpLCB2LmVuZCgpLCB2YWx1ZSkKI2RlZmluZSBTT1JUKCB2ICkgc29ydCh2LmJlZ2luKCksIHYuZW5kKCkpCiNkZWZpbmUgU09SVEModiwgY29tcCkgc29ydCh2LmJlZ2luKCksIHYuZW5kKCksIGNvbXApCiNkZWZpbmUgV1coIHggKSBjb3V0PDwjeDw8IiA9ICI8PCh4KTw8IlxuIjsKI2RlZmluZSBlbmRsICdcbicKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZzIG1hdHJpejsKdmkgcG9udGNvbXAsIG1pbngsIG1pbnksIG1heHgsIG1heHk7CnZ2aSBjb21wOwppbnQgWCwgWSwgcXRkZV9jdXN0b21lcnMsIHF0ZGVfb2ZmaWNlczsKCnZvaWQgcHJpbnQoKXsKICAgIGxvb3AoWCkKICAgICAgICBjb3V0IDw8IG1hdHJpeltpXSA8PCBlbmRsOwp9CgoKc3RydWN0IEN1c3RvbWVyewogICAgaW50IHgsIHksIHBvbnRvcywgY29tcG9uZW50ZTsKICAgIEN1c3RvbWVyKGludCBhLCBpbnQgYiwgaW50IGMpewogICAgICAgIHggPSBhOwogICAgICAgIHkgPSBiOwogICAgICAgIHBvbnRvcyA9IGM7CiAgICAgICAgY29tcG9uZW50ZSA9IDA7CiAgICB9Cn07Cgp2ZWN0b3I8Q3VzdG9tZXI+IGN1c3RvbWVyczsKCmludCBwZXNvKHBpaSBwb3MpewogICAgY2hhciBvcCA9IG1hdHJpeltwb3MuZl1bcG9zLnNdOwogICAgaWYob3A9PScjJykgcmV0dXJuIElORjsKICAgIGlmKG9wPT0nficpIHJldHVybiA4MDA7CiAgICBpZihvcD09JyonKSByZXR1cm4gMjAwOwogICAgaWYob3A9PSdYJykgcmV0dXJuIDEyMDsKICAgIGlmKG9wPT0nXycpIHJldHVybiAxMDA7CiAgICBpZihvcD09J0gnKSByZXR1cm4gNzA7CiAgICBpZihvcD09J1QnKSByZXR1cm4gNTA7Cn0KCnBhaXI8aW50LCBzdHJpbmc+IGRpamtzdHJhIChwaWkgb3JpZ2VtLCBwaWkgZGVzdGlubyl7CiAgICBpbnQgZGlzdFtUQU1dW1RBTV07CiAgICBjaGFyIHByZXZbVEFNXVtUQU1dOwogICAgZm9yKGludCBpPTA7IGk8VEFNOyBpKyspCiAgICAgICAgZm9yKGludCBqPTA7IGo8VEFNOyBqKyspCiAgICAgICAgewogICAgICAgICAgICBkaXN0W2ldW2pdID0gSU5GOwogICAgICAgICAgICBwcmV2W2ldW2pdID0gJ1gnOwogICAgICAgIH0gICAgCiAgICBzZXQ8IHBhaXI8aW50LCBwaWk+ID4gZmlsYTsKICAgIGZpbGEuaW5zZXJ0KG1wKDAsIG9yaWdlbSkpOwogICAgZGlzdFtvcmlnZW0uZl1bb3JpZ2VtLnNdID0gMDsKICAgIHdoaWxlKCFmaWxhLmVtcHR5KCkpewoJCWNvdXQgPDwgZmlsYS5iZWdpbigpLT5zZWNvbmQuZmlyc3QgPDwgIiAiIDw8IGZpbGEuYmVnaW4oKS0+cy5zIDw8ICJcbiI7CiAgICAgICAgcGlpIHZlcnRpY2UgPSBmaWxhLmJlZ2luKCktPnNlY29uZDsKICAgICAgICBpbnQgZGlzdGFuY2lhID0gZGlzdFt2ZXJ0aWNlLmZdW3ZlcnRpY2Uuc107CiAgICAgICAgaW50IHBlcyA9IHBlc28odmVydGljZSk7IAogICAgICAgIGZpbGEuZXJhc2UoKmZpbGEuYmVnaW4oKSk7CiAgICAgICAgaW50IG1vdmVzX3hbXSA9IHswLCAwLCAxLCAtMX07CiAgICAgICAgaW50IG1vdmVzX3lbXSA9IHsxLCAtMSwgMCwgMH07CiAgICAgICAgY2hhciBkaXJbXSA9IHsnUicsICdMJywgJ0QnLCAnVSd9OwogICAgICAgIGZvcihpbnQgaT0wOyBpPDQ7IGkrKyl7CiAgICAgICAgICAgIGludCBhdHVhbFggPSBtb3Zlc194W2ldK3ZlcnRpY2UuZjsKICAgICAgICAgICAgaW50IGF0dWFsWSA9IG1vdmVzX3lbaV0rdmVydGljZS5zOwogICAgICAgICAgICBpZihhdHVhbFg+PTAgYW5kIGF0dWFsWDxYIGFuZCBhdHVhbFk+PTAgYW5kIGF0dWFsWTxZKXsKICAgICAgICAgICAgICAgIGlmKGRpc3RbYXR1YWxYXVthdHVhbFldID4gZGlzdGFuY2lhICsgcGVzKXsKICAgICAgICAgICAgICAgICAgICBkaXN0W2F0dWFsWF1bYXR1YWxZXSA9IGRpc3RhbmNpYSArIHBlczsKICAgICAgICAgICAgICAgICAgICBwcmV2W2F0dWFsWF1bYXR1YWxZXSA9IGRpcltpXTsKICAgICAgICAgICAgICAgICAgICBmaWxhLmluc2VydChtcChkaXN0W2F0dWFsWF1bYXR1YWxZXSwgbXAoYXR1YWxYLCBhdHVhbFkpKSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CiAgICBzdHJpbmcgczsKICAgIHBpaSBjdXIgPSBkZXN0aW5vOwogICAgd2hpbGUgKGN1ciAhPSBvcmlnZW0pCiAgICB7CiAgICAgICAgcyArPSBwcmV2W2N1ci5mXVtjdXIuc107CiAgICAgICAgaWYgKHByZXZbY3VyLmZdW2N1ci5zXSA9PSAnVScpCiAgICAgICAgICAgIGN1ci5mKys7CiAgICAgICAgZWxzZSBpZiAocHJldltjdXIuZl1bY3VyLnNdID09ICdEJykKICAgICAgICAgICAgY3VyLmYtLTsKICAgICAgICBlbHNlIGlmIChwcmV2W2N1ci5mXVtjdXIuc10gPT0gJ1InKQogICAgICAgICAgICBjdXIucy0tOwogICAgICAgIGVsc2UgaWYgKHByZXZbY3VyLmZdW2N1ci5zXSA9PSAnTCcpCiAgICAgICAgICAgIGN1ci5zKys7ICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgICAgZWxzZQogICAgCXsKICAgIAkJcyArPSAnWCc7CiAgICAJCWJyZWFrOwogICAgCX0KICAgIH0KICAgIHN0cmluZyBzMiAocy5yYmVnaW4oKSwgcy5yZW5kKCkpOwogICAgcmV0dXJuIG1wKGRpc3RbZGVzdGluby5mXVtkZXN0aW5vLnNdLCBzMik7Cn0KCmJvb2wgZGZzIChpbnQgeCwgaW50IHksIGludCBjKQp7CiAgICBpZiAoeCA8IDAgb3IgeCA+PSBYIG9yIHkgPCAwIG9yIHkgPj0gWSBvciBtYXRyaXpbeF1beV0gPT0gJyMnIG9yIGNvbXBbeF1beV0gPiAwKQogICAgICAgIHJldHVybiBmYWxzZTsKICAgIGNvbXBbeF1beV0gPSBjOwogICAgZGZzKHggLSAxLCB5LCBjKTsKICAgIGRmcyh4LCB5IC0gMSwgYyk7CiAgICBkZnMoeCArIDEsIHksIGMpOwogICAgZGZzKHgsIHkgKyAxLCBjKTsKICAgIHJldHVybiB0cnVlOwp9CgppbnQgaW5pdF9jb21wICgpCnsKICAgIHZpIGF1eCAoWSwgMCk7CiAgICBjb21wLmFzc2lnbihYLCBhdXgpOwogICAgaW50IGMgPSAxOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBYOyBpKyspCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBZOyBqKyspCiAgICAgICAgICAgIGlmIChkZnMoaSwgaiwgYykpCiAgICAgICAgICAgICAgICBjKys7CiAgICBwb250Y29tcC5hc3NpZ24oYywgMCk7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHF0ZGVfY3VzdG9tZXJzOyBpKyspCiAgICB7CiAgICAgICAgcG9udGNvbXBbY29tcFtjdXN0b21lcnNbaV0ueF1bY3VzdG9tZXJzW2ldLnldXSArPSBjdXN0b21lcnNbaV0ucG9udG9zOwogICAgICAgIGN1c3RvbWVyc1tpXS5jb21wb25lbnRlID0gY29tcFtjdXN0b21lcnNbaV0ueF1bY3VzdG9tZXJzW2ldLnldOwogICAgfQogICAgbWlueC5hc3NpZ24oYywgVEFNKTsgCiAgICBtaW55LmFzc2lnbihjLCBUQU0pOwogICAgbWF4eC5hc3NpZ24oYywgLTEpOwogICAgbWF4eS5hc3NpZ24oYywgLTEpOwogICAgZm9yIChpbnQgaSA9IDA7IGkgPCBYOyBpKyspCiAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBZOyBqKyspCiAgICAgICAgeyAgICAKICAgICAgICAgICAgbWlueFtjb21wW2ldW2pdXSA9IG1pbihtaW54W2NvbXBbaV1bal1dLCBpKTsKICAgICAgICAgICAgbWlueVtjb21wW2ldW2pdXSA9IG1pbihtaW55W2NvbXBbaV1bal1dLCBqKTsKICAgICAgICAgICAgbWF4eFtjb21wW2ldW2pdXSA9IG1heChtYXh4W2NvbXBbaV1bal1dLCBpKTsKICAgICAgICAgICAgbWF4eVtjb21wW2ldW2pdXSA9IG1heChtYXh5W2NvbXBbaV1bal1dLCBqKTsgICAgICAgICAgIAogICAgICAgIH0KICAgIGludCBjb250ID0gMDsKICAgIGZvciAoaW50IGkgOiBwb250Y29tcCkKICAgICAgICBpZiAoaSA+IDApCiAgICAgICAgICAgIGNvbnQrKzsKICAgIHJldHVybiBjb250Owp9CgovKgpwaWkgYmluYXJ5X3NlYXJjaCAoaW50IGMpCnsKICAgIGludCBtaW5YID0gbWlueFtjXTsKICAgIGludCBtaW5ZID0gbWlueVtjXTsKICAgIGludCBtYXhZID0gbWF4eVtjXTsKICAgIGludCBtYXhYID0gbWF4eFtjXTsKICAgIHBpaSBwb3MgPSBtcCgobWluWCttYXhYKS8yLCAobWluWSttYXhZKS8yKTsKICAgIHdoaWxlKHBlc28ocG9zKSE9SU5GKXsKICAgICAgICAKICAgIH0KICAgIAogICAgcmV0dXJuIHBvczsKfSovCgppbnQgbWFpbiAoKSB7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbiA+PiBZID4+IFggPj4gcXRkZV9jdXN0b21lcnMgPj4gcXRkZV9vZmZpY2VzOwogICAgCiAgICAKICAgIGxvb3AocXRkZV9jdXN0b21lcnMpewogICAgICAgIGludCBhLCBiLCBjOwogICAgICAgIGNpbiA+PiBhID4+IGIgPj4gYzsKICAgICAgICBjdXN0b21lcnMucGIoQ3VzdG9tZXIoYiwgYSwgYykpOwogICAgfQogICAgCiAgICBsb29wKFgpewogICAgICAgIHN0cmluZyBhOwogICAgICAgIGNpbiA+PiBhOwogICAgICAgIG1hdHJpei5wYihhKTsKICAgIH0KICAgIAogICAgY291dCA8PCBpbml0X2NvbXAoKSA8PCBlbmRsOwogICAgcHJpbnQoKTsKICAgIAogICAgaW50IHB4LCBweSwgcXgsIHF5OwogICAgd2hpbGUgKGNpbiA+PiBweCA+PiBweSA+PiBxeCA+PiBxeSkKICAgIHsKICAgIAlhdXRvIHAgPSBkaWprc3RyYShtcChweCwgcHkpLCBtcChxeCwgcXkpKTsKICAgIAljb3V0IDw8IHAuZiA8PCAiICIgPDwgcC5zIDw8ICJcbiI7CiAgICB9CgogIHJldHVybiAwOwp9